Matroid Secretary Problems

DOI10.1145/3212512MaRDI QIDQ4625656zbMATH OpenOpenAlexWikidataFDO

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)

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

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)