Approximation algorithms for knapsack problems with cardinality constraints

DOI10.1016/S0377-2217(99)00261-1zbMath0961.90131WikidataQ58826485 ScholiaQ58826485MaRDI QIDQ1569936

Hans Kellerer, David Pisinger, Alberto Caprara, Ulrich Pferschy

Publication date: 9 July 2000

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

dynamic programmingpackingknapsack problemapproximation algorithms

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (52)

Approximation schemes for knapsack problems with shelf divisions ⋮ Multistage knapsack ⋮ The Subset Sum game ⋮ Approximation algorithms for hard capacitated \(k\)-facility location problems ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ Polynomial time approximation schemes for class-constrained packing problems ⋮ On the complexity of working set selection ⋮ Integer knapsack problems with set-up weights ⋮ Exact solution of the robust knapsack problem ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Tight bounds for online class-constrained packing ⋮ Product sequencing and pricing under cascade browse model ⋮ Randomized strategies for cardinality robustness in the knapsack problem ⋮ Reoptimizing the 0-1 knapsack problem ⋮ Computing knapsack solutions with cardinality robustness ⋮ On approximating the incremental knapsack problem ⋮ Approximate strong separation with application in fractional graph coloring and preemptive scheduling. ⋮ Minimum and worst-case performance ratios of rollout algorithms ⋮ Randomized strategies for robust combinatorial optimization with approximate separation ⋮ Bin packing with general cost structures ⋮ Scheduling of inventory releasing jobs to minimize a regular objective function of delivery times ⋮ A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem ⋮ Committee selection under weight constraints ⋮ Approximability of the two-stage stochastic knapsack problem with discretely distributed weights ⋮ Reductions between scheduling problems with non-renewable resources and knapsack problems ⋮ Two-dimensional knapsack-block packing problem ⋮ A new effective dynamic program for an investment optimization problem ⋮ Order acceptance and scheduling with consideration of service level ⋮ \(L\)-class enumeration algorithms for a discrete production planning problem with interval resource quantities ⋮ A new exact approach for the 0-1 collapsing knapsack problem ⋮ An approximation algorithm for a competitive facility location problem with network effects ⋮ Network pollution games ⋮ Minimal cost reconfiguration of data placement in a storage area network ⋮ Greedy algorithm for the general multidimensional knapsack problem ⋮ Optimization models for targeted offers in direct marketing: exact and heuristic algorithms ⋮ An efficient algorithm for the collapsing knapsack problem ⋮ Hybrid rounding techniques for knapsack problems ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ Unnamed Item ⋮ Bounding the Running Time of Algorithms for Scheduling and Packing Problems ⋮ Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study ⋮ A faster FPTAS for knapsack problem with cardinality constraint ⋮ Truthful approximation mechanisms for restricted combinatorial auctions ⋮ On the Proximity of the Optimal Values of the Multi-dimensional Knapsack Problem with and Without the Cardinality Constraint ⋮ New Results for Network Pollution Games ⋮ There is no EPTAS for two-dimensional knapsack ⋮ Modified subset sum heuristics for bin packing ⋮ A faster FPTAS for knapsack problem with cardinality constraint ⋮ Offline black and white bin packing ⋮ An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem ⋮ Robust online algorithms for dynamic choosing problems ⋮ Optimal Genetic Screening for Cystic Fibrosis

Uses Software

• Knapsack

Cites Work

• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Linear time algorithms for some separable quadratic programming problems
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Heuristic algorithms for the multiple knapsack problem
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A fast algorithm for strongly correlated knapsack problems
• A new fully polynomial time approximation scheme for the Knapsack problem
• Simple but efficient approaches for the collapsing knapsack problem
• Time bounds for selection
• A new linear storage, polynomial-time approximation scheme for the subset-sum problem
• Computational study of a column generation algorithm for bin packing and cutting stock problems
• Fast Approximation Algorithms for Knapsack Problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• The Collapsing 0–1 Knapsack Problem
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithms for knapsack problems with cardinality constraints