Submodular maximization with uncertain knapsack capacity

DOI10.1137/18M1174428zbMATH1437.90138WikidataQ127566653MaRDI 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)

zbMATH Keywords

knapsack problemrobust optimizationsubmodular maximization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Robustness in mathematical programming (90C17)

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

Cites work

• A Unified Continuous Greedy Algorithm for Submodular Maximization
• A note on maximizing a submodular set function subject to a knapsack constraint
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Adaptivity gaps for stochastic probing: submodular and XOS functions
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Computing knapsack solutions with cardinality robustness
• Dual techniques for scheduling on a machine with varying speed
• Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: extended abstract
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (extended abstract)
• Maximizing a monotone submodular function subject to a matroid constraint
• On the performance of Smith's rule in single-machine scheduling with nonlinear cost
• Online contention resolution schemes
• Packing a knapsack of unknown capacity
• Randomized strategies for cardinality robustness in the knapsack problem
• Submodular stochastic probing on matroids
• Universal sequencing on an unreliable machine

Cited in

(6)

• Packing a knapsack of unknown capacity
• Fractionally subadditive maximization under an incremental knapsack constraint
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• Non-submodular maximization with matroid and knapsack constraints
• Submodular maximization with uncertain knapsack capacity
• Maximizing expected utility over a 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)