|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 7 of 10 found articles
| Title: |
New polynomial-time instances to various knapsack-type problems |
| Author: |
Isto Aho |
| Appeared in: |
Fundamenta informaticae |
| Paging: | Volume 53 (2003) nr. 3-4 pages 199-228 |
| Year: |
2003-07-11 |
| Contents: |
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. |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 7 of 10 found articles
| << previous | next >> |