Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)

DOI10.1007/978-3-642-22935-0_19zbMath1343.90077OpenAlexW28813714MaRDI QIDQ3088096

Roy Schwartz, Moran Feldman, Joseph (Seffi) Naor

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_19

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Related Items (13)

Prophet Secretary ⋮ Shrinking maxima, decreasing costs: new online packing and covering problems ⋮ The simulated greedy algorithm for several submodular matroid secretary problems ⋮ Online crowdsourced truck delivery using historical information ⋮ Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints ⋮ The Temp Secretary Problem ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ The Submodular Secretary Problem Goes Linear ⋮ A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem ⋮ Online Submodular Maximization with Preemption ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Who solved the secretary problem
• Improved Algorithms and Analysis for Secretary Problems and Generalizations
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• Maximizing Non-monotone Submodular Functions
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Competitive Weighted Matching in Transversal Matroids
• Secretary Problems via Linear Programming
• Submodular Secretary Problem and Extensions
• A Knapsack Secretary Problem with Applications
• The Secretary Problem and Its Extensions: A Review
• Symmetry and Approximability of Submodular Maximization Problems
• On Maximizing Welfare When Utility Functions Are Subadditive
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Dynamic Programming and Decision Theory
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

This page was built for publication: Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)