Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.16zbMath1467.68225arXiv1607.08805MaRDI QIDQ5002619

Thomas Kesselheim, Andreas Tönnis

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1607.08805

zbMATH Keywords

online algorithms; secretary problem; submodular maximization

Mathematics Subject Classification ID

90C27: Combinatorial optimization

68W20: Randomized algorithms

68W27: Online algorithms; streaming algorithms

Related Items

Unnamed Item, Unnamed Item, Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online, Packing returning secretaries, Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints, New results for the \(k\)-secretary problem

Cites Work

• Unnamed Item
• The simulated greedy algorithm for several submodular matroid secretary problems
• Geometry of Online Packing Linear Programs
• An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
• Online Submodular Welfare Maximization
• Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
• Improved Approximations for k-Exchange Systems
• The Submodular Secretary Problem Goes Linear
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Primal beats dual on online packing LPs in the random-order model
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Online submodular welfare maximization: Greedy is optimal
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties