TY - GEN
T1 - Combinatorial prophet inequalities
AU - Rubinstein, Aviad
AU - Singla, Sahil
N1 - Publisher Copyright:
Copyright © by SIAM.
PY - 2017
Y1 - 2017
N2 - We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For a (non-monotone) submodular objective function over an arbitrary matroid feasibility constraint, we give an O(1)-competitive algorithm. For a monotone subadditive objective function over an arbitrary downwardclosed feasibility constraint, we give an O(log n log2 r) competitive algorithm (where r is the cardinality of the largest feasible subset). Inspired by the proof of our subadditive prophet inequality, we also obtain an O(log n log2 r)-competitive algorithm for the Secretary Problem with a monotone subadditive objective function subject to an arbitrary downward-closed feasibility constraint. Even for the special case of a cardinality feasibility constraint, our algorithm circumvents an ( p n) lower bound by Bateni, Hajiaghayi, and Zadimoghaddam [10] in a restricted query model. En route to our submodular prophet inequality, we prove a technical result of independent interest: we show a variant of the Correlation Gap Lemma [14, 1] for nonmonotone submodular functions.
AB - We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For a (non-monotone) submodular objective function over an arbitrary matroid feasibility constraint, we give an O(1)-competitive algorithm. For a monotone subadditive objective function over an arbitrary downwardclosed feasibility constraint, we give an O(log n log2 r) competitive algorithm (where r is the cardinality of the largest feasible subset). Inspired by the proof of our subadditive prophet inequality, we also obtain an O(log n log2 r)-competitive algorithm for the Secretary Problem with a monotone subadditive objective function subject to an arbitrary downward-closed feasibility constraint. Even for the special case of a cardinality feasibility constraint, our algorithm circumvents an ( p n) lower bound by Bateni, Hajiaghayi, and Zadimoghaddam [10] in a restricted query model. En route to our submodular prophet inequality, we prove a technical result of independent interest: we show a variant of the Correlation Gap Lemma [14, 1] for nonmonotone submodular functions.
UR - http://www.scopus.com/inward/record.url?scp=85016202747&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85016202747&partnerID=8YFLogxK
U2 - 10.1137/1.9781611974782.110
DO - 10.1137/1.9781611974782.110
M3 - Conference contribution
AN - SCOPUS:85016202747
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1671
EP - 1687
BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
A2 - Klein, Philip N.
PB - Association for Computing Machinery
T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
Y2 - 16 January 2017 through 19 January 2017
ER -