A simple O((rank))-competitive algorithm for the matroid secretary problem

DOI10.1287/MOOR.2017.0876MaRDI QIDQ5219558zbMATH OpenOpenAlexFDO

Authors Moran Feldman, Ola Svensson, Rico Zenklusen

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

matroidsonline algorithmssecretary problem

Mathematics Subject Classification ID

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

Recommendations

• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Improved competitive ratio for the matroid secretary problem
• Matroid secretary problem in the random-assignment model
• Matroid secretary problem in the random assignment model
• Matroid Secretary Problems

Cites work

• A multiple-choice secretary algorithm with applications to online auctions
• Advances on matroid secretary problems: free order model and laminar case
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Competitive weighted matching in transversal matroids
• Dynamic Programming and Decision Theory
• Improved competitive ratio for the matroid secretary problem
• Improved competitive ratios for submodular secretary problems (extended abstract)
• Matroid secretary problem in the random-assignment model
• Matroids, secretary problems, and online mechanisms
• Prophet Inequalities with Limited Information
• Secretary problems with convex costs
• Secretary problems: laminar matroid and interval scheduling
• Submodular secretary problem and extensions
• The simulated greedy algorithm for several submodular matroid secretary problems
• Who solved the secretary problem? With comments and a rejoinder by the author

Cited in

(18)

• Improved online algorithms for knapsack and GAP in the random order model
• Formal barriers to simple algorithms for the matroid secretary problem
• The secretary recommendation problem
• Strong algorithms for the ordinal matroid secretary problem
• Packing returning secretaries
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Improved competitive ratio for the matroid secretary problem
• Online contention resolution schemes with applications to Bayesian selection problems
• 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
• Generalized assignment and knapsack problems in the random-order model
• Matroid secretary via labeling schemes
• Constant-competitiveness for random assignment matroid secretary without knowing the matroid
• Online combinatorial assignment in independence systems
• Online combinatorial assignment in independence systems
• Laminar matroid secretary: greedy strikes back

This page was built for publication: A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem

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