On variants of the matroid secretary problem

DOI10.1007/s00453-013-9795-yzbMath1307.68101arXiv1104.4081OpenAlexW2567949245MaRDI QIDQ2017872

Shayan Oveis Gharan, Jan Vondrák

Publication date: 23 March 2015

Published in: Algorithmica, Algorithms – ESA 2011 (Search for Journal in Brave)

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

zbMATH Keywords

matroidssecretary problemonline optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (12)

The simulated greedy algorithm for several submodular matroid secretary problems ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Constant-competitiveness for random assignment matroid secretary without knowing the matroid ⋮ The best-or-worst and the postdoc problems with random number of candidates ⋮ Generalized Sequential Stochastic Assignment Problem ⋮ Matroid prophet inequalities and applications to multi-dimensional mechanism design ⋮ Online \((J, K)\)-search problem and its competitive analysis ⋮ Prior independent mechanisms via prophet inequalities with limited information ⋮ Optimal composition ordering problems for piecewise linear functions ⋮ A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem ⋮ Online k-max Search Algorithms with Applications to the Secretary Problem ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Who solved the secretary problem? With comments and a rejoinder by the author
• Competitive Weighted Matching in Transversal Matroids
• Secretary Problems via Linear Programming
• Online Stochastic Packing Applied to Display Ad Allocation
• Submodular Secretary Problem and Extensions
• The Secretary Problem with an Unknown Number of Options
• The secretary problem with an unknown number of candidates
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Dynamic Programming and Decision Theory

This page was built for publication: On variants of the matroid secretary problem