A fast algorithm for strongly correlated knapsack problems

DOI10.1016/S0166-218X(98)00127-9zbMath0921.90122WikidataQ58826511 ScholiaQ58826511MaRDI QIDQ1281395

David Pisinger

Publication date: 22 March 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

dynamic programmingexact algorithmsurrogate relaxationmemorizationfixed-charge problemsubset-sum problem0--1 knapsack problem2-optimal heuristicstrongly correlated knapsack-problems

Mathematics Subject Classification ID

Dynamic programming (90C39) Boolean programming (90C09)

Related Items (6)

Integer knapsack problems with set-up weights ⋮ An exact approach for the bilevel knapsack problem with interdiction constraints and extensions ⋮ Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem ⋮ An incomplete \(m\)-exchange algorithm for solving the large-scale multi-scenario knapsack problem ⋮ Approximation algorithms for knapsack problems with cardinality constraints ⋮ Optimal Genetic Screening for Cystic Fibrosis

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• A lexicographic search for strongly correlated 0-1 knapsack problems
• Simple but efficient approaches for the collapsing knapsack problem
• An expanding-core algorithm for the exact \(0-1\) knapsack problem
• An Algorithm for Large Zero-One Knapsack Problems
• Facets of the knapsack polytope
• A Minimal Algorithm for the 0-1 Knapsack Problem
• Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems

This page was built for publication: A fast algorithm for strongly correlated knapsack problems