Beyond matroids: secretary problem and prophet inequality with general constraints

DOI10.1145/2897518.2897540MaRDI QIDQ5361840zbMATH OpenOpenAlexFDO

Authors Aviad Rubinstein

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

prophet inequalitysecretary problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Abstract: We study generalizations of the "Prophet Inequality" and "Secretary Problem", where the algorithm is restricted to an arbitrary downward-closed set system. For {0,1}-values, we give O(log n)-competitive algorithms for both problems. This is close to the Omega(log n / loglog n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log n log r)-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(log r loglog n) factors) an open question posed to us by Bobby Kleinberg.

Recommendations

• Combinatorial prophet inequalities
• Matroid prophet inequalities
• Prophet secretary for combinatorial auctions and matroids
• Matroid Secretary Problems
• Matroids, secretary problems, and online mechanisms

Cited in

(34)

• Stable secretaries
• The secretary recommendation problem
• Finding the second-best candidate under the Mallows model
• Prophet inequalities vs. approximating optimum online
• From pricing to prophets, and back!
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• Combinatorial prophet inequalities
• Strong algorithms for the ordinal matroid secretary problem
• Optimal online contention resolution schemes via ex-ante prophet inequalities
• Prophet matching with general arrivals
• Prophet inequalities for independent and identically distributed random variables from an unknown distribution
• A Framework for the Secretary Problem on the Intersection of Matroids
• Packing returning secretaries
• Hiring secretaries over time: the benefit of concurrent employment
• Tight revenue gaps among simple mechanisms
• Matroid prophet inequalities
• An O(\log \log m) Prophet Inequality for Subadditive Combinatorial Auctions
• Packing returning secretaries
• Optimal prophet inequality with less than one sample
• Optimal stopping with multi-dimensional comparative loss aversion
• The importance of knowing the arrival order in combinatorial Bayesian settings
• Prophet inequalities via the expected competitive ratio
• On submodular prophet inequalities and correlation gap
• Prophet secretary for combinatorial auctions and matroids
• Order-competitive ratio
• The outer limits of contention resolution on matroids and connections to the secretary problem
• Simple and optimal online contention resolution schemes for k-uniform matroids
• Prophet upper bounds for online matching and auctions
• From contention resolution to matroid secretary and back
• Online combinatorial assignment in independence systems
• Pairwise-independent contention resolution
• Matroid Bayesian online selection
• Online combinatorial assignment in independence systems
• Pairwise-independent contention resolution

This page was built for publication: Beyond matroids: secretary problem and prophet inequality with general constraints

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