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 (7)

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

This page was built for publication: Randomized strategies for cardinality robustness in the knapsack problem