TY - GEN

T1 - Discrete stochastic submodular maximization

T2 - 9th International Conference on Algorithms and Complexity, CIAC 2015

AU - Hellerstein, Lisa

AU - Kletenik, Devorah

AU - Lin, Patrick

PY - 2015

Y1 - 2015

N2 - We consider the problem of stochastic monotone submodular function maximization, subject to constraints. We give results on adaptivity gaps, and on the gap between the optimal offline and online solutions. We present a procedure that transforms a decision tree (adaptive algorithm) into a non-adaptive chain. We prove that this chain achieves at least T times the utility of the decision tree, over a product distribution and binary state space, where T = mini,j Pr[xi = j]. This proves an adaptivity gap of 1/T (which is 2 in the case of a uniform distribution) for the problem of stochastic monotone submodular maximization subject to state-independent constraints. For a cardinality constraint, we prove that a simple adaptive greedy algorithm achieves an approximation factor of (1 – 1/eT) with respect to the optimal offline solution; previously, it has been proven that the algorithm achieves an approximation factor of (1 – 1/e) with respect to the optimal adaptive online solution. Finally, we show that there exists a non-adaptive solution for the stochastic max coverage problem that is within a factor (1− 1/e) of the optimal adaptive solution and within a factor of T (1 – 1/e) of the optimal offline solution.

AB - We consider the problem of stochastic monotone submodular function maximization, subject to constraints. We give results on adaptivity gaps, and on the gap between the optimal offline and online solutions. We present a procedure that transforms a decision tree (adaptive algorithm) into a non-adaptive chain. We prove that this chain achieves at least T times the utility of the decision tree, over a product distribution and binary state space, where T = mini,j Pr[xi = j]. This proves an adaptivity gap of 1/T (which is 2 in the case of a uniform distribution) for the problem of stochastic monotone submodular maximization subject to state-independent constraints. For a cardinality constraint, we prove that a simple adaptive greedy algorithm achieves an approximation factor of (1 – 1/eT) with respect to the optimal offline solution; previously, it has been proven that the algorithm achieves an approximation factor of (1 – 1/e) with respect to the optimal adaptive online solution. Finally, we show that there exists a non-adaptive solution for the stochastic max coverage problem that is within a factor (1− 1/e) of the optimal adaptive solution and within a factor of T (1 – 1/e) of the optimal offline solution.

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

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

U2 - 10.1007/978-3-319-18173-8_17

DO - 10.1007/978-3-319-18173-8_17

M3 - Conference contribution

AN - SCOPUS:84944728286

SN - 9783319181721

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

SP - 235

EP - 248

BT - Algorithms and Complexity - 9th International Conference, CIAC 2015, Proceedings

A2 - Widmayer, Peter

A2 - Paschos, Vangelis Th.

PB - Springer Verlag

Y2 - 20 May 2015 through 22 May 2015

ER -