Scenario submodular cover

Nathaniel Grammel; Lisa Hellerstein; Devorah Kletenik; Patrick Lin

doi:10.1007/978-3-319-51741-4_10

Scenario submodular cover

Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik, Patrick Lin

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We introduce the Scenario Submodular Cover problem. In this problem, the goal is to produce a cover with minimum expected cost, with respect to an empirical joint probability distribution, given as input by a weighted sample of realizations. The problem is a counterpart to the Stochastic Submodular Cover problem studied by Golovin and Krause [6], which assumes independent variables. We give two approximation algorithms for Scenario Submodular Cover. Assuming an integervalued utility function and integer weights, the first achieves an approximation factor of O(logQm), where m is the sample size and Q is the goal utility. The second, simpler algorithm achieves an approximation factor of O(logQW), where W is the sum of the weights. We achieve our bounds by building on previous related work (in [4,6,15]) and by exploiting a technique we call the Scenario-OR modification. We apply these algorithms to a new problem, Scenario Boolean Function Evaluation. Our results have applciations to other problems involving distributions that are explicitly specified by their support.

Original language	English (US)
Title of host publication	Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers
Editors	Monaldo Mastrolilli, Klaus Jansen
Publisher	Springer Verlag
Pages	116-128
Number of pages	13
ISBN (Print)	9783319517407
DOIs	https://doi.org/10.1007/978-3-319-51741-4_10
State	Published - 2017
Event	14th International Workshop on Approximation and Online Algorithms, WAOA 2016 - Aarhus, Denmark Duration: Aug 25 2016 → Aug 26 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10138 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	14th International Workshop on Approximation and Online Algorithms, WAOA 2016
Country/Territory	Denmark
City	Aarhus
Period	8/25/16 → 8/26/16

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-51741-4_10

Cite this

Grammel, N., Hellerstein, L., Kletenik, D., & Lin, P. (2017). Scenario submodular cover. In M. Mastrolilli, & K. Jansen (Eds.), Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers (pp. 116-128). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10138 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-51741-4_10

Scenario submodular cover. / Grammel, Nathaniel; Hellerstein, Lisa; Kletenik, Devorah et al.

Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. ed. / Monaldo Mastrolilli; Klaus Jansen. Springer Verlag, 2017. p. 116-128 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10138 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Grammel, N, Hellerstein, L, Kletenik, D & Lin, P 2017, Scenario submodular cover. in M Mastrolilli & K Jansen (eds), Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10138 LNCS, Springer Verlag, pp. 116-128, 14th International Workshop on Approximation and Online Algorithms, WAOA 2016, Aarhus, Denmark, 8/25/16. https://doi.org/10.1007/978-3-319-51741-4_10

Grammel N, Hellerstein L, Kletenik D, Lin P. Scenario submodular cover. In Mastrolilli M, Jansen K, editors, Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. Springer Verlag. 2017. p. 116-128. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-51741-4_10

Grammel, Nathaniel ; Hellerstein, Lisa ; Kletenik, Devorah et al. / Scenario submodular cover. Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. editor / Monaldo Mastrolilli ; Klaus Jansen. Springer Verlag, 2017. pp. 116-128 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5d3779d938be4347bfec471e2421deed,

title = "Scenario submodular cover",

abstract = "We introduce the Scenario Submodular Cover problem. In this problem, the goal is to produce a cover with minimum expected cost, with respect to an empirical joint probability distribution, given as input by a weighted sample of realizations. The problem is a counterpart to the Stochastic Submodular Cover problem studied by Golovin and Krause [6], which assumes independent variables. We give two approximation algorithms for Scenario Submodular Cover. Assuming an integervalued utility function and integer weights, the first achieves an approximation factor of O(logQm), where m is the sample size and Q is the goal utility. The second, simpler algorithm achieves an approximation factor of O(logQW), where W is the sum of the weights. We achieve our bounds by building on previous related work (in [4,6,15]) and by exploiting a technique we call the Scenario-OR modification. We apply these algorithms to a new problem, Scenario Boolean Function Evaluation. Our results have applciations to other problems involving distributions that are explicitly specified by their support.",

author = "Nathaniel Grammel and Lisa Hellerstein and Devorah Kletenik and Patrick Lin",

note = "Funding Information: The work in this paper was supported by NSF Grant 1217968. L. Hellerstein thanks Andreas Krause for useful discussions at ETH, and for directing our attention to the bound of Streeter and Golovin for min-sum submodular cover. We thank an anonymous referee for suggesting the Kosaraju trick. Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th International Workshop on Approximation and Online Algorithms, WAOA 2016 ; Conference date: 25-08-2016 Through 26-08-2016",

year = "2017",

doi = "10.1007/978-3-319-51741-4_10",

language = "English (US)",

isbn = "9783319517407",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "116--128",

editor = "Monaldo Mastrolilli and Klaus Jansen",

booktitle = "Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers",

}

TY - GEN

T1 - Scenario submodular cover

AU - Grammel, Nathaniel

AU - Hellerstein, Lisa

AU - Kletenik, Devorah

AU - Lin, Patrick

N1 - Funding Information: The work in this paper was supported by NSF Grant 1217968. L. Hellerstein thanks Andreas Krause for useful discussions at ETH, and for directing our attention to the bound of Streeter and Golovin for min-sum submodular cover. We thank an anonymous referee for suggesting the Kosaraju trick. Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - We introduce the Scenario Submodular Cover problem. In this problem, the goal is to produce a cover with minimum expected cost, with respect to an empirical joint probability distribution, given as input by a weighted sample of realizations. The problem is a counterpart to the Stochastic Submodular Cover problem studied by Golovin and Krause [6], which assumes independent variables. We give two approximation algorithms for Scenario Submodular Cover. Assuming an integervalued utility function and integer weights, the first achieves an approximation factor of O(logQm), where m is the sample size and Q is the goal utility. The second, simpler algorithm achieves an approximation factor of O(logQW), where W is the sum of the weights. We achieve our bounds by building on previous related work (in [4,6,15]) and by exploiting a technique we call the Scenario-OR modification. We apply these algorithms to a new problem, Scenario Boolean Function Evaluation. Our results have applciations to other problems involving distributions that are explicitly specified by their support.

AB - We introduce the Scenario Submodular Cover problem. In this problem, the goal is to produce a cover with minimum expected cost, with respect to an empirical joint probability distribution, given as input by a weighted sample of realizations. The problem is a counterpart to the Stochastic Submodular Cover problem studied by Golovin and Krause [6], which assumes independent variables. We give two approximation algorithms for Scenario Submodular Cover. Assuming an integervalued utility function and integer weights, the first achieves an approximation factor of O(logQm), where m is the sample size and Q is the goal utility. The second, simpler algorithm achieves an approximation factor of O(logQW), where W is the sum of the weights. We achieve our bounds by building on previous related work (in [4,6,15]) and by exploiting a technique we call the Scenario-OR modification. We apply these algorithms to a new problem, Scenario Boolean Function Evaluation. Our results have applciations to other problems involving distributions that are explicitly specified by their support.

UR - http://www.scopus.com/inward/record.url?scp=85010695278&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010695278&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-51741-4_10

DO - 10.1007/978-3-319-51741-4_10

M3 - Conference contribution

AN - SCOPUS:85010695278

SN - 9783319517407

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 116

EP - 128

BT - Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers

A2 - Mastrolilli, Monaldo

A2 - Jansen, Klaus

PB - Springer Verlag

T2 - 14th International Workshop on Approximation and Online Algorithms, WAOA 2016

Y2 - 25 August 2016 through 26 August 2016

ER -

Scenario submodular cover

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this