On equivalent knapsack problems
type: Item
instance of: scholarly article
title: On equivalent knapsack problems
zbMATH Open document ID: 0602.90103
DOI: 10.1016/0166-218X(86)90030-2
author: B. George
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: By aggregating objective function and constraint of a knapsack problem max\(\{\) c'x\(|\) a'x\(\leq b\), \(x\geq 0\) integral\(\}\) an equivalent problem of the following form is obtained: Let \(t=[c_ 1b/a_ 1]+1\) and let \(F(z)=\min \{(c+ta)'x|\) c'x\(\equiv z mod t\), \(x\geq 0\), integral\(\}\). Then z is an optimal value of the given problem if it is maximal subject to \(0\leq z<t\) and \(z+tb\geq F(z)\). Such a value z can be determined by dynamic programming with recursion: \(F(z)=\min_{j}(c_ j+ta_ j+F(z-c_ j))\). This procedure can be speeded up by calculating a recursion only for the values \(1,2,...,c_ 1-1\). Since the classical recursions use computation modulo \(a_ 1\), the new method might be advantageous if \(c_ 1<a_ 1\).
reviewed by: Rainer E. Burkard
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3972638
zbMATH Keywords: corner polyhedron
zbMATH Keywords: group knapsack
zbMATH Keywords: aggregating objective function and constraint
zbMATH Keywords: knapsack problem
MaRDI profile type: Publication
cites work: Q5595961
cites work: Q3214706
description: scientific article; zbMATH DE number 3972638