Submodular Maximization with Uncertain Knapsack Capacity
From MaRDI portal
Publication:5232144
DOI10.1137/18M1174428zbMath1437.90138WikidataQ127566653 ScholiaQ127566653MaRDI QIDQ5232144
Hanna Sumita, Yasushi Kawase, Takuro Fukunaga
Publication date: 29 August 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Combinatorial optimization (90C27) Approximation algorithms (68W25) Robustness in mathematical programming (90C17)
Related Items
Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows, Fractionally subadditive maximization under an incremental knapsack constraint, Non-Submodular Maximization with Matroid and Knapsack Constraints
Cites Work
- Unnamed Item
- A note on maximizing a submodular set function subject to a knapsack constraint
- Randomized strategies for cardinality robustness in the knapsack problem
- Computing knapsack solutions with cardinality robustness
- Universal Sequencing on an Unreliable Machine
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
- Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
- Dual Techniques for Scheduling on a Machine with Varying Speed
- Submodular Stochastic Probing on Matroids
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Online Contention Resolution Schemes
- Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
- On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
- Packing a Knapsack of Unknown Capacity
- Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
