Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
From MaRDI portal
Publication:5002619
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
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