The Submodular Secretary Problem Goes Linear
From MaRDI portal
Publication:4637502
DOI10.1137/16M1105220zbMath1390.68769arXiv1507.08384OpenAlexW2796215898WikidataQ130035903 ScholiaQ130035903MaRDI QIDQ4637502
Publication date: 24 April 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.08384
Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Online algorithms; streaming algorithms (68W27)
Related Items
Prophet Secretary, Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints, A Framework for the Secretary Problem on the Intersection of Matroids, Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, Packing returning secretaries, Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints, Secretary markets with local information, Unnamed Item, Unnamed Item, Online algorithms for the maximum \(k\)-interval coverage problem, Online Contention Resolution Schemes with Applications to Bayesian Selection Problems, Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The simulated greedy algorithm for several submodular matroid secretary problems
- Who solved the secretary problem
- Submodular functions and electrical networks
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Competitive weighted matching in transversal matroids
- Matroid Secretary Problem in the Random-Assignment Model
- Secretary Problems with Convex Costs
- Submodular secretary problem and extensions
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
- Maximizing Non-monotone Submodular Functions
- A Knapsack Secretary Problem with Applications
- The Secretary Problem and Its Extensions: A Review
- Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- 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
- Prophet Inequalities with Limited Information
- Submodular Maximization with Cardinality Constraints
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Dynamic Programming and Decision Theory
