Combinatorial prophet inequalities

DOI10.1137/1.9781611974782.110MaRDI QIDQ4575853zbMATH OpenOpenAlexFDO

Authors Aviad Rubinstein, Sahil Singla

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.00665

zbMATH Keywords

secretary problemprophet inequalitiescombinatorial valuation functionsmonotone subadditive objective function

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26) Stopping times; optimal stopping problems; gambling theory (60G40)

Abstract: 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 downward-closed feasibility constraint, we give an $O(lognlo{g}^{2}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(logncdotlo{g}^{2}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 $Omega(sqrtn)$ lower bound by Bateni, Hajiaghayi, and Zadimoghaddam cite{BHZ13-submodular-secretary_original} 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 for non-monotone submodular functions.

Recommendations

• Beyond matroids: secretary problem and prophet inequality with general constraints
• Prophet secretary for combinatorial auctions and matroids
• Submodular secretary problem and extensions
• Matroid prophet inequalities
• Submodular secretary problem and extensions

Cited in

(33)

• Prophet secretary for combinatorial auctions and matroids
• Strong algorithms for the ordinal matroid secretary problem
• On the correlation gap of matroids
• scientific article; zbMATH DE number 7651221 (Why is no real title available?)
• Pairwise independent correlation gap
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• IID prophet inequality with a single data point
• From pricing to prophets, and back!
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
• An O(\log \log m) Prophet Inequality for Subadditive Combinatorial Auctions
• Making individually fair predictions with causal pathways
• Pairwise-independent contention resolution
• Matroid Bayesian online selection
• Tight revenue gaps among simple mechanisms
• Optimal stopping with multi-dimensional comparative loss aversion
• Prophet inequalities via the expected competitive ratio
• Pairwise-independent contention resolution
• Polymatroid Prophet Inequalities
• Hiring secretaries over time: the benefit of concurrent employment
• On submodular prophet inequalities and correlation gap
• Prophet Inequalities with Limited Information
• Streaming adaptive submodular maximization
• Stochastic submodular probing with state-dependent costs
• Stochastic submodular probing with state-dependent costs
• Streaming adaptive submodular maximization
• On the correlation gap of matroids
• Prophet secretary for combinatorial auctions and matroids
• Prophet inequalities for independent and identically distributed random variables from an unknown distribution
• A constant factor prophet inequality for online combinatorial auctions
• Simple and optimal online contention resolution schemes for k-uniform matroids
• Beyond matroids: secretary problem and prophet inequality with general constraints
• scientific article; zbMATH DE number 7378727 (Why is no real title available?)

This page was built for publication: Combinatorial prophet inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575853)