Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
From MaRDI portal
Publication:5002619
DOI10.4230/LIPIcs.APPROX-RANDOM.2017.16zbMath1467.68225arXiv1607.08805OpenAlexW2963126409MaRDI QIDQ5002619
Thomas Kesselheim, Andreas Tönnis
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1607.08805
Combinatorial optimization (90C27) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (6)
Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints ⋮ New results for the \(k\)-secretary problem ⋮ Packing returning secretaries ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online
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
This page was built for publication: Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
