|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 7 van 10 gevonden artikelen
| Titel: |
New polynomial-time instances to various knapsack-type problems |
| Auteur: |
Isto Aho |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 53 (2003) nr. 3-4 pagina's 199-228 |
| Jaar: |
2003-07-11 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 7 van 10 gevonden artikelen
| << vorige | volgende >> |