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/

[1] Deza M. M., Loran M., Geometriya razrezov i metrik, MTsNMO, M., 2001 | MR

[2] Nonnengart A., Weidenbach C., “Computing small clause normal forms”, Handbook of Automated Reasoning, eds. A. Robinson, A. Voronkov, Elsevier Science and MIT Press, 2001, 335–367 | Zbl

[3] Billera L. J., Sarangarajan A., “All $0$–$1$ polytopes are travelling salesman polytopes”, Combinatorica, 16 (1996), 175–188 | DOI | MR | Zbl

[4] Maksimenko A. N., “Mnogogranniki zadachi o vypolnimosti yavlyayutsya granyami mnogogrannika zadachi kommivoyazhera”, Diskretn. analiz i issledov. operatsii, 18:3 (2011), 76–83 | MR | Zbl

[5] Karp R. M., “Reducibility among combinatorial problems”, Complexity of Computer Computations, eds. R. E. Miller, J. W. Thatcher, Plenum Press, 1972, 85–103 | DOI | MR

[6] Padberg M. W., “Equivalent knapsack-type formulations of bounded integer linear programs: an alternative approach”, Naval Research Logistics Quarterly, 19:4 (1972), 699–708 | DOI | MR | Zbl

[7] Kovalev M. M., Diskretnaya optimizatsiya (tselochislennoe programmirovanie), BGU, Minsk, 1977 | MR

[8] Orman A. J., Williams H. P., “A survey of different integer programming formulations of the travelling salesman problem”, Optimization, Econometric and Financial Analysis, Springer, 2007, 91–104 | DOI

[9] Grötschel M., Jünger M., Reinelt G., “Facets of the linear ordering polytope”, Math. Program., 33:1 (1985), 43–60 | DOI | MR

[10] Bondarenko V. A., “Ob odnom kombinatornom mnogogrannike”, Modelir. i analiz vychisl. sistem, Yaroslavl, 1987, 133–134 | MR

[11] Maksimenko A. N., “Mnogogrannik zadachi o ryukzake”, Vopr. teorii grupp i gomologicheskoi algebry, YarGU, Yaroslavl, 2003, 163–172

[12] Maksimenko A. N., “O kombinatornykh svoistvakh mnogogrannika dvoinykh pokrytii”, Tez. dokl. XIV Vserossiisk. konf. “Matematicheskoe programmirovanie i prilozheniya”, Informatsionnyi byulleten Assotsiatsii matematicheskogo programmirovaniya, 12, UrO RAN, Ekaterinburg, 2011, 197–198

[13] Maksimenko A. N., “Ob universalnykh svoistvakh mnogogrannika razrezov”, Problemy teoreticheskoi kibernetiki, Materialy XVI mezhdunarodn. konf., Izd-vo Nizhegorodsk. un-ta, 2011, 294–296

[14] Yannakakis M., “Expressing combinatorial optimization problems by linear programs”, J. Comput. System Sci., 43:3 (1991), 441–466 | DOI | MR | Zbl