The simulated greedy algorithm for several submodular matroid secretary problems

DOI10.1007/S00224-015-9642-4MaRDI QIDQ290918zbMATH OpenOpenAlexFDO

Authors Tengyu Ma, Bo Tang, Yajun Wang

Publication date 3 June 2016

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2013/3958/

zbMATH Keywords

matroidsecretary problemsubmodular function

Mathematics Subject Classification ID

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

Recommendations

• The simulated greedy algorithm for several submodular matroid secretary problems
• Matroid Secretary Problems
• Matroids, secretary problems, and online mechanisms
• Submodular secretary problems: cardinality, matching, and linear constraints
• Submodular secretary problem and extensions

Cites work

• A Knapsack Secretary Problem with Applications
• A multiple-choice secretary algorithm with applications to online auctions
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Competitive weighted matching in transversal matroids
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• scientific article; zbMATH DE number 3383344 (Why is no real title available?)
• 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
• Secretary problems: laminar matroid and interval scheduling
• Secretary problems: weights and discounts
• Submodular secretary problem and extensions
• The Secretary Problem and Its Extensions: A Review
• Who solved the secretary problem

Cited in

(12)

• Monotone k-submodular secretary problems: cardinality and knapsack constraints
• Prior independent mechanisms via prophet inequalities with limited information
• The simulated greedy algorithm for several submodular matroid secretary problems
• The submodular secretary problem goes linear
• Strong algorithms for the ordinal matroid secretary problem
• Submodular secretary problems: cardinality, matching, and linear constraints
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Non-adaptive prophet inequalities for minor-closed classes of matroids
• Generalized assignment and knapsack problems in the random-order model
• Single sample prophet inequality for uniform matroids of rank 2
• Constant-competitiveness for random assignment matroid secretary without knowing the matroid
• Laminar matroid secretary: greedy strikes back

This page was built for publication: The simulated greedy algorithm for several submodular matroid secretary problems

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