Geodesic
The common face of some $0/1$-polytopes with NP-complete nonadjacency relation
Fundamentalʹnaâ i prikladnaâ matematika, Tome 18 (2013) no. 2, pp. 105-118.

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

In this paper, we consider so-called double covering polytopes. In 1995, Matsui showed that the problem of checking nonadjacency on these polytopes is NP-complete. We show that double covering polytopes are faces of the following polytopes: knapsack polytopes, set covering polytopes, cubic subgraph polytopes, $3$-SAT polytopes, partial order polytopes, traveling salesman polytopes, and some others. 
@article{FPM_2013_18_2_a7,
     author = {A. N. Maksimenko},
     title = {The common face of some $0/1$-polytopes with {NP-complete} nonadjacency relation},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {105--118},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2013_18_2_a7/}
}
TY  - JOUR
AU  - A. N. Maksimenko
TI  - The common face of some $0/1$-polytopes with NP-complete nonadjacency relation
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2013
SP  - 105
EP  - 118
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2013_18_2_a7/
LA  - ru
ID  - FPM_2013_18_2_a7
ER  - 
%0 Journal Article
%A A. N. Maksimenko
%T The common face of some $0/1$-polytopes with NP-complete nonadjacency relation
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2013
%P 105-118
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2013_18_2_a7/
%G ru
%F FPM_2013_18_2_a7
A. N. Maksimenko. The common face of some $0/1$-polytopes with NP-complete nonadjacency relation. Fundamentalʹnaâ i prikladnaâ matematika, Tome 18 (2013) no. 2, pp. 105-118. http://geodesic.mathdoc.fr/item/FPM_2013_18_2_a7/

[1] Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost v kombinatornoi optimizatsii, LKI, M., 2008

[2] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[3] Deza M. M., Loran M., Geometriya razrezov i metrik, MTsNMO, M., 2001

[4] Emelichev V. A., Kovalëv M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, M., 1981 | MR | Zbl

[5] Kovalëv M. M., Diskretnaya optimizatsiya (tselochislennoe programmirovanie), BGU, Minsk, 1977 | MR

[6] Maksimenko A. N., “Kombinatornye svoistva mnogogrannika zadachi o kratchaishem puti”, ZhVM i MF, 44:9 (2004), 1693–1696 | MR | Zbl

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

[8] Maksimenko A. N., “Ob affinnoi svodimosti kombinatornykh mnogogrannikov”, Dokl. RAN, 443:6 (2012), 661–663 | MR | Zbl

[9] Alfakih A. Y., Murty K. G., “Adjacency on the constrained assignment problem”, Discrete Appl. Math., 87:1 (1998), 269–274 | DOI | MR | Zbl

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

[11] Bondarenko V. A., Yurov S. V., “About a polyhedron of cubic graphs”, Fund. Inform., 25:1 (1996), 35–38 | MR | Zbl

[12] Chung S.-J., Structural Complexity of Adjacency on $0$-$1$ Convex Polytopes, PhD thesis, Univ. of Michigan, 1980

[13] Fiorini S., “A combinatorial study of partial order polytopes”, Eur. J. Combin., 24:2 (2003), 149–159 | DOI | MR | Zbl

[14] Fiorini S., Massar S., Pokutta S., Tiwary H. R., de Wolf R., Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds, 2011, arXiv: 1111.0837v3

[15] Geist D., Rodin E. Y., “Adjacency of the $0$-$1$ knapsack problem”, Comput. Operat. Res., 19:8 (1992), 797–800 | DOI | MR | Zbl

[16] Hausmann D., Adjacency on Polytopes in Combinatorial Optimization, Math. Systems Econ., 49, A. Hain, Konigstein, 1980 | MR | Zbl

[17] Junger M., Reinelt G., Rinaldi G., “The traveling salesman problem”, Network Models, Handbooks in Operations Research and Management Science, 7, Elsevier, Amsterdam, 1995, 225–330 | DOI | MR

[18] Letchford A. N., “The general routing polyhedron: a unifying framework”, Eur. J. Operat. Res., 112:1 (1999), 122–133 | DOI | Zbl

[19] Matsui T., “NP-completeness of non-adjacency relations on some $0$-$1$-polytopes”, Operations Research with Applications in Engineering, Technology and Management, Int. Symp. 1st., Lect. Notes Operat. Res., 1, Beijing World Publ., 1995, 249–258

[20] Matsui T., Tamura S., “Adjacency on combinatorial polyhedra”, Discrete Appl. Math., 56 (1995), 311–321 | DOI | MR | Zbl

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

[22] Papadimitriou C. H., “The adjacency relation on the traveling salesman polytope is NP-complete”, Math. Programming, 14:1 (1978), 312–324 | DOI | MR | Zbl

[23] Salazar-Gonzalez J.-J., “The Steiner cycle polytope”, Eur. J. Operat. Res., 147:3 (2003), 671–679 | DOI | MR | Zbl

[24] Toktas B., Yen J. W., Zabinsky Z. B., “Addressing capacity uncertainty in resource-constrained assignment problems”, Comput. Operat. Res., 33:3 (2006), 724–745 | DOI | Zbl

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