New polynomial-time instances to various knapsack-type problems

Article type: Research Article

Authors: Aho, Isto

Affiliations: Department of Computer and Information Sciences, University of Tampere, FIN-33014, Finland

Abstract: We describe a special case of the interactive knapsack optimization problem (motivated by the load clipping problem) solvable in polynomial time. Given an instance parameterized by k, the solution can be found in polynomial time, where the polynomial has degree k. In the interactive knapsack problem, $k$ is connected to the length induced by an item. A similar construction solves a special case of the 0–1 multi-dimensional knapsack and the 0–1 linear integer programming problems in polynomial time. In these problems the parameter determines the width of the restriction matrix, which is a band matrix. We extend the 0–1 multi-dimensional knapsack solution to 0–n multi-dimensional knapsack problems (and to 0–n IP problems). Our algorithms are based on the (resource bounded) shortest path search: we represent restrictions efficiently in a form of a graph such that each feasible solution has a path between given source and target vertices.

Keywords: Knapsack-type problems, longest path, polynomial-time instances

Journal: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 199-228, 2002