The simulated greedy algorithm for several submodular matroid secretary problems

DOI10.1007/s00224-015-9642-4zbMath1339.68343OpenAlexW1529760171MaRDI QIDQ290918

F. Blanchet-Sadri, M. Dambrine

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

submodular functionmatroidsecretary problem

Mathematics Subject Classification ID

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

Related Items (6)

Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ The Submodular Secretary Problem Goes Linear ⋮ Prior independent mechanisms via prophet inequalities with limited information ⋮ A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Who solved the secretary problem
• On variants of the matroid secretary problem
• Competitive weighted matching in transversal matroids
• Matroid Secretary Problem in the Random-Assignment Model
• Submodular secretary problem and extensions
• Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
• A Knapsack Secretary Problem with Applications
• The Secretary Problem and Its Extensions: A Review
• Matroid Secretary for Regular and Decomposable Matroids
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

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