Submodular maximization with uncertain knapsack capacity
From MaRDI portal
Publication:5232144
DOI10.1137/18M1174428zbMATH Open1437.90138WikidataQ127566653 ScholiaQ127566653MaRDI QIDQ5232144FDOQ5232144
Authors: Yasushi Kawase, Hanna Sumita, Takuro Fukunaga 
Publication date: 29 August 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Recommendations
- Submodular maximization with uncertain knapsack capacity
- Maximizing expected utility over a knapsack constraint
- Robust monotone submodular function maximization
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Robust monotone submodular function maximization
Combinatorial optimization (90C27) Approximation algorithms (68W25) Robustness in mathematical programming (90C17)
Cites Work
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (extended abstract)
- Maximizing a monotone submodular function subject to a matroid constraint
- Approximating the stochastic Knapsack problem: the benefit of adaptivity
- Online contention resolution schemes
- Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: extended abstract
- Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
- A note on maximizing a submodular set function subject to a knapsack constraint
- Adaptive submodularity: theory and applications in active learning and stochastic optimization
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Packing a knapsack of unknown capacity
- Randomized strategies for cardinality robustness in the knapsack problem
- Computing knapsack solutions with cardinality robustness
- On the performance of Smith's rule in single-machine scheduling with nonlinear cost
- Universal sequencing on an unreliable machine
- Submodular stochastic probing on matroids
- Adaptivity gaps for stochastic probing: submodular and XOS functions
- Dual techniques for scheduling on a machine with varying speed
Cited In (6)
- Maximizing expected utility over a knapsack constraint
- Packing a knapsack of unknown capacity
- Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
- Submodular maximization with uncertain knapsack capacity
- Non-submodular maximization with matroid and knapsack constraints
- Fractionally subadditive maximization under an incremental knapsack constraint
This page was built for publication: Submodular maximization with uncertain knapsack capacity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232144)
