Randomized strategies for cardinality robustness in the knapsack problem

DOI10.1016/j.tcs.2016.12.019zbMath1380.90237OpenAlexW2293386763MaRDI QIDQ1675929

Yusuke Kobayashi, Kenjiro Takazawa

Publication date: 3 November 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://tsukuba.repo.nii.ac.jp/?action=repository_action_common_download&item_id=44551&item_no=1&attribute_id=17&file_no=1

zbMATH Keywords

exchangeabilityknapsack problemrandomized strategyrobust independence system

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Other game-theoretic models (91A40) Randomized algorithms (68W20)

Related Items

Packing a Knapsack of Unknown Capacity, Randomized strategies for robust combinatorial optimization with approximate separation, Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows, Robust Randomized Matchings, Submodular Maximization with Uncertain Knapsack Capacity, Fractionally subadditive maximization under an incremental knapsack constraint, General bounds for incremental maximization

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Approximation algorithms for knapsack problems with cardinality constraints
• Computing knapsack solutions with cardinality robustness
• Packing a Knapsack of Unknown Capacity
• Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty
• An Analysis of the Greedy Heuristic for Independence Systems
• Robust Matchings
• Randomized Strategies for Cardinality Robustness in the Knapsack Problem
• Robust randomized matchings
• Greedy in Approximation Algorithms
• Robust Matchings and Matroid Intersections
• Robust Independence Systems