Submodular maximization with uncertain knapsack capacity

DOI10.1137/18M1174428zbMATH Open1437.90138WikidataQ127566653 ScholiaQ127566653MaRDI QIDQ5232144FDOQ5232144

Hanna Sumita, Yasushi Kawase, 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

zbMATH Keywords

knapsack problemrobust optimizationsubmodular maximization

Mathematics Subject Classification ID

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
• 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
• Title not available (Why is that?)
• 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 (3)

• Non-Submodular Maximization with Matroid and Knapsack Constraints
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• 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)