A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

DOI10.1287/moor.2017.0876zbMath1435.68376OpenAlexW2782298540MaRDI QIDQ5219558

Moran Feldman, Rico Zenklusen, Ola Svensson

Publication date: 12 March 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2017.0876

zbMATH Keywords

online algorithmsmatroidssecretary problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Stopping times; optimal stopping problems; gambling theory (60G40) Combinatorial aspects of matroids and geometric lattices (05B35) Online algorithms; streaming algorithms (68W27)

Related Items (9)

The secretary recommendation problem ⋮ Constant-competitiveness for random assignment matroid secretary without knowing the matroid ⋮ Packing returning secretaries ⋮ Machine covering in the random-order model ⋮ Knapsack secretary through boosting ⋮ Unnamed Item ⋮ Improved online algorithms for Knapsack and GAP in the random order model ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The simulated greedy algorithm for several submodular matroid secretary problems
• Who solved the secretary problem? With comments and a rejoinder by the author
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On variants of the matroid secretary problem
• Competitive weighted matching in transversal matroids
• Matroid Secretary Problem in the Random-Assignment Model
• Secretary Problems with Convex Costs
• An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
• Submodular secretary problem and extensions
• Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
• Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
• Matroid Secretary for Regular and Decomposable Matroids
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Prophet Inequalities with Limited Information
• Dynamic Programming and Decision Theory

This page was built for publication: A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem