Geodesic
An analog of the Cook theorem for polytopes
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 8 (2012), pp. 34-42

Voir la notice de l'article provenant de la source Math-Net.Ru

We prove that the polytope $M$ of any combinatorial optimization problem with a linear objective function is an affine image of a face of the cut polytope whose dimension is polynomial with respect to the dimension of $M$.
Keywords: combinatorial optimization, cut polytope, knapsack polytope, faces, polynomial reducibility of problems. 
@article{IVM_2012_8_a3,
     author = {A. N. Maksimenko},
     title = {An analog of the {Cook} theorem for polytopes},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {34--42},
     publisher = {mathdoc},
     number = {8},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2012_8_a3/}
}
TY  - JOUR
AU  - A. N. Maksimenko
TI  - An analog of the Cook theorem for polytopes
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2012
SP  - 34
EP  - 42
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2012_8_a3/
LA  - ru
ID  - IVM_2012_8_a3
ER  - 
%0 Journal Article
%A A. N. Maksimenko
%T An analog of the Cook theorem for polytopes
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2012
%P 34-42
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2012_8_a3/
%G ru
%F IVM_2012_8_a3
A. N. Maksimenko. An analog of the Cook theorem for polytopes. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 8 (2012), pp. 34-42. http://geodesic.mathdoc.fr/item/IVM_2012_8_a3/