Computing knapsack solutions with cardinality robustness

DOI10.1007/S13160-012-0075-ZMaRDI QIDQ1926647zbMATH OpenOpenAlexFDO

Authors Naonori Kakimura, Kazuhisa Makino, 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

robustnessFPTASNP-hardnessknapsack problems

Mathematics Subject Classification ID

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

Recommendations

• Computing knapsack solutions with cardinality robustness
• Complexity results and exact algorithms for robust knapsack problems
• On the robust knapsack problem
• Randomized strategies for cardinality robustness in the knapsack problem
• Randomized strategies for cardinality robustness in the knapsack problem

Cites work

• scientific article; zbMATH DE number 5764868 (Why is no real title available?)
• scientific article; zbMATH DE number 3544074 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1302173 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A general approach for incremental approximation and hierarchical clustering
• A new fully polynomial time approximation scheme for the Knapsack problem
• Algorithm Theory - SWAT 2004
• An Analysis of the Greedy Heuristic for Independence Systems
• Approximation algorithms for knapsack problems with cardinality constraints
• Computing knapsack solutions with cardinality robustness
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Matroids and the greedy algorithm
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Note on Independence Functions
• Robust Matchings
• Robust discrete optimization and its applications
• Robust independence systems
• Robust matchings and matroid intersections
• Robust optimization
• The Online Median Problem

Cited in

(15)

• Submodular maximization with uncertain knapsack capacity
• The multi-band robust knapsack problem -- a dynamic programming approach
• General bounds for incremental maximization
• Exact solution of the robust knapsack problem
• scientific article; zbMATH DE number 7366679 (Why is no real title available?)
• Robust randomized matchings
• Randomized strategies for robust combinatorial optimization with approximate separation
• The lexicographic \(\alpha \)-robust knapsack problem
• Computing knapsack solutions with cardinality robustness
• Randomized strategies for cardinality robustness in the knapsack problem
• On the robust knapsack problem
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• Randomized strategies for cardinality robustness in the knapsack problem
• Complexity results and exact algorithms for robust knapsack problems
• Fractionally subadditive maximization under an incremental knapsack constraint

Describes a project that uses

Uses Software

• Knapsack

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1926647)