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 -