Combinatorial prophet inequalities

DOI10.1137/1.9781611974782.110zbMATH Open1417.91251arXiv1611.00665OpenAlexW2950198148MaRDI QIDQ4575853FDOQ4575853

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)

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.

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

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

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)

Cited In (26)

• Strong algorithms for the ordinal matroid secretary problem
• Title not available (Why is that?)
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• From pricing to prophets, and back!
• Title not available (Why is that?)
• 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
• Tight revenue gaps among simple mechanisms
• Optimal stopping with multi-dimensional comparative loss aversion
• Prophet inequalities via the expected competitive ratio
• Polymatroid Prophet Inequalities
• Hiring secretaries over time: the benefit of concurrent employment
• On submodular prophet inequalities and correlation gap
• Prophet Inequalities with Limited Information
• Stochastic submodular probing with state-dependent costs
• Stochastic submodular probing with state-dependent costs
• Streaming adaptive submodular maximization
• 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
• Beyond matroids: secretary problem and prophet inequality with general constraints
• Title not available (Why is that?)
• Prophet secretary for combinatorial auctions and matroids

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)