Geodesic
A Quasi-Polynomial Algorithm for the Knapsack Problem
Yugoslav journal of operations research, Tome 4 (1994) no. 2, p. 149 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

The main result of the paper is a quasi-polynomial algorithm for generating the external points (vertices) of the Knapsack Polytope . The complexity of this algorithm (for fixed dimension) is better than the complexity of all the known quasipolynomial algorithms for this problem. The idea is similar to this one used by Haies and Larman [2]. Our improvement is based on obtaining of new upper bounds for the number of the vertices of the Knapsack Polytope. The algorithm can be applied directly to solve the Knapsack Problem with arbitrary convex objective function.
Keywords: Knapsack, convex criterion, quasi- polynomial algorithm 
@article{YJOR_1994_4_2_a1,
     author = {Valentin E. Brimkov},
     title = {A {Quasi-Polynomial} {Algorithm} for the {Knapsack} {Problem}},
     journal = {Yugoslav journal of operations research},
     pages = {149 },
     year = {1994},
     volume = {4},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_1994_4_2_a1/}
}
TY  - JOUR
AU  - Valentin E. Brimkov
TI  - A Quasi-Polynomial Algorithm for the Knapsack Problem
JO  - Yugoslav journal of operations research
PY  - 1994
SP  - 149 
VL  - 4
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/YJOR_1994_4_2_a1/
LA  - en
ID  - YJOR_1994_4_2_a1
ER  - 
%0 Journal Article
%A Valentin E. Brimkov
%T A Quasi-Polynomial Algorithm for the Knapsack Problem
%J Yugoslav journal of operations research
%D 1994
%P 149 
%V 4
%N 2
%U http://geodesic.mathdoc.fr/item/YJOR_1994_4_2_a1/
%G en
%F YJOR_1994_4_2_a1
Valentin E. Brimkov. A Quasi-Polynomial Algorithm for the Knapsack Problem. Yugoslav journal of operations research, Tome 4 (1994) no. 2, p. 149 . http://geodesic.mathdoc.fr/item/YJOR_1994_4_2_a1/