Computing knapsack solutions with cardinality robustness

DOI10.1007/s13160-012-0075-zzbMath1258.68184OpenAlexW1994753237MaRDI QIDQ1926647

Kazuhisa Makino, Naonori Kakimura, Kento Seimi

Publication date: 28 December 2012

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13160-012-0075-z

zbMATH Keywords

robustnessNP-hardnessFPTASknapsack problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Approximation algorithms (68W25)

Related Items (7)

Randomized strategies for cardinality robustness in the knapsack problem ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem
• Robust discrete optimization and its applications
• Approximation algorithms for knapsack problems with cardinality constraints
• Computing Knapsack Solutions with Cardinality Robustness
• Note on Independence Functions
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• An Analysis of the Greedy Heuristic for Independence Systems
• The Online Median Problem
• Robust Matchings
• Algorithm Theory - SWAT 2004
• A General Approach for Incremental Approximation and Hierarchical Clustering
• Matroids and the greedy algorithm
• Robust Independence Systems
• Robust Matchings and Matroid Intersections

This page was built for publication: Computing knapsack solutions with cardinality robustness