Startseite > Publikationen > Publikationen

Publikationen

Meyer auf der Heide, Friedhelm:

A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem.

J. ACM 31(3): S. 668-676, Jul. 1984

Abstract

A linear search algorithm that recogmzes the n-dimensional knapsack problem in 2n^(4) log n + O(n^3) steps is presented. Tills algorithm works for inputs consisting of n numbers for some arbitrary but fixed integer n. T'nis result s~olves an open problem posed by Dobkin/Lipton and A.C.C. Yao, among others, and it destroys the hope of proving nonpolynomial lower bounds for this NP-complete problem in the model of linear search algorithms.

Dateien

hni1951.pdf



Bibtex

@article{hniid=1951,
author = {Meyer auf der Heide, Friedhelm},
title = {A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem},
journal = {J. ACM},
volume = {31(3)},
pages = {668-676},
month = jul,
year = {1984},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/1951