Matroid Secretary Problems

DOI10.1145/3212512MaRDI QIDQ4625656zbMATHOpenAlexWikidataFDO

Authors Moshe Babaioff, Nicole Immorlica, David Kempe, Robert D. Kleinberg

Publication date 25 February 2019

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3212512

zbMATH Keywords

online algorithmscompetitive ratiomatroidsmechanism designsecretary problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• Secretary problem: graphs, matroids and greedoids
• Matroid secretary problem in the random assignment model
• Matroid secretary problem in the random-assignment model
• A framework for the secretary problem on the intersection of matroids
• A Framework for the Secretary Problem on the Intersection of Matroids
• Matroids, secretary problems, and online mechanisms
• The matroid secretary problem for minor-closed classes and random matroids
• Secretary Problems via Linear Programming

Cited in

(38)

• Beyond matroids: secretary problem and prophet inequality with general constraints
• Secretary markets with local information
• The simulated greedy algorithm for several submodular matroid secretary problems
• Advances on matroid secretary problems: free order model and laminar case
• Matroids, secretary problems, and online mechanisms
• Knapsack secretary through boosting
• Online matroid intersection: beating half for random arrival
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Combinatorial secretary problems with ordinal information
• Improved online algorithm for fractional knapsack in the random order model
• New results for the \(k\)-secretary problem
• Strong algorithms for the ordinal matroid secretary problem
• Strong algorithms for the ordinal matroid secretary problem
• Packing returning secretaries
• A framework for the secretary problem on the intersection of matroids
• Formal barriers to simple algorithms for the matroid secretary problem
• The secretary recommendation problem
• Constant-competitiveness for random assignment matroid secretary without knowing the matroid
• Submodular secretary problem and extensions
• A Framework for the Secretary Problem on the Intersection of Matroids
• Online independent set beyond the worst-case: secretaries, prophets, and periods
• Machine covering in the random-order model
• Approximate tradeoffs on weighted labeled matroids
• The matroid secretary problem for minor-closed classes and random matroids
• Secretary problems: laminar matroid and interval scheduling
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Secretary and online matching problems with machine learned advice
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Improved online algorithms for knapsack and GAP in the random order model
• Submodular secretary problem and extensions
• House markets with matroid and knapsack constraints
• Scheduling In the random-order model
• Improved competitive ratio for the matroid secretary problem
• The simulated greedy algorithm for several submodular matroid secretary problems
• Secretary problem: graphs, matroids and greedoids
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• Matroid secretary problem in the random-assignment model
• Matroid secretary problem in the random assignment model

This page was built for publication: Matroid Secretary Problems

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