New polynomial-time instances to various knapsack-type problems

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.