Geodesic
A special role of Boolean quadratic polytopes among other combinatorial polytopes
Modelirovanie i analiz informacionnyh sistem, Tome 23 (2016) no. 1, pp. 23-40.

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

We consider several families of combinatorial polytopes associated with the following NP-complete problems: maximum cut, Boolean quadratic programming, quadratic linear ordering, quadratic assignment, set partition, set packing, stable set, $3$-assignment. For comparing two families of polytopes we use the following method. We say that a family $P$ is affinely reduced to a family $Q$ if for every polytope $p\in P$ there exists $q\in Q$ such that $p$ is affinely equivalent to $q$ or to a face of $q$, where $\dim q = O((\dim p)^k)$ for some constant $k$. Under this comparison the above-mentioned families are splitted into two equivalence classes. We show also that these two classes are simpler (in the above sense) than the families of polytopes of the following problems: set covering, traveling salesman, $0$-$1$ knapsack problem, $3$-satisfiability, cubic subgraph, partial ordering. In particular, Boolean quadratic polytopes appear as faces of polytopes in every mentioned families. Article is published in the author's wording.
Keywords: NP-hard problems, affine reduction, faces of polytopes. 
@article{MAIS_2016_23_1_a2,
     author = {A. N. Maksimenko},
     title = {A special role of {Boolean} quadratic polytopes among other combinatorial polytopes},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {23--40},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2016_23_1_a2/}
}
TY  - JOUR
AU  - A. N. Maksimenko
TI  - A special role of Boolean quadratic polytopes among other combinatorial polytopes
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2016
SP  - 23
EP  - 40
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2016_23_1_a2/
LA  - en
ID  - MAIS_2016_23_1_a2
ER  - 
%0 Journal Article
%A A. N. Maksimenko
%T A special role of Boolean quadratic polytopes among other combinatorial polytopes
%J Modelirovanie i analiz informacionnyh sistem
%D 2016
%P 23-40
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2016_23_1_a2/
%G en
%F MAIS_2016_23_1_a2
A. N. Maksimenko. A special role of Boolean quadratic polytopes among other combinatorial polytopes. Modelirovanie i analiz informacionnyh sistem, Tome 23 (2016) no. 1, pp. 23-40. http://geodesic.mathdoc.fr/item/MAIS_2016_23_1_a2/

[1] D. Avis, H. R. Tiwary, “On the Extension Complexity of Combinatorial Polytopes”, Automata, Languages, and Programming, Lecture Notes in Computer Science, 7965, Springer, 2013, 57–68 | DOI | MR | Zbl

[2] E. Balas, M. J. Saltzman, “Facets of the three-index assignment polytope”, Discrete Applied Mathematics, 23:3 (1989), 201–229 | DOI | MR | Zbl

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

[4] V. A. Bondarenko, A. N. Maksimenko, Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii, LKI, M., 2008, 184 pp.

[5] C. Buchheim, A. Wiegele, L. Zheng, “Exact Algorithms for the Quadratic Linear Ordering Problem”, Informs J. on Computing, 22:1 (2010), 168–177 | DOI | MR | Zbl

[6] V. Chvatal, “On certain polytopes associated with graphs”, J. Combin. Theory, Ser. B, 18 (1975), 138–154 | DOI | MR | Zbl

[7] M. Conforti, G. Cornuéjols, G. Zambelli, “Extended formulations in combinatorial optimization”, A Quarterly Journal of Operations Research, 8:1 (2010), 1–48 | MR | Zbl

[8] G. B. Dantzig, D. R. Fulkerson, S. M. Johnson, “Solution of a large-scale traveling salesman problem”, Operation Research, 2:4 (1954), 393–410 | MR

[9] C. De Simone, “The cut polytope and the Boolean quadric polytope”, Discrete Math., 79 (1990), 71–75 | DOI | MR | Zbl

[10] M. M. Deza, M. Laurent, Geometry of cuts and metrics, Springer, 1997, 588 pp. | MR | Zbl

[11] R. Euler, “Odd cycles and a class of facets of the axial 3-index assignment polytope”, Applicationes Mathematicae (Zastosowania Matematyki), 19 (1987), 375–386 | MR | Zbl

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

[13] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, “Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds”, Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, ACM, New York, 2012, 95–106 | MR | Zbl

[14] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman Co., New York, 1979, 340 pp. | MR | Zbl

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

[16] V. Kaibel, Polyhedral combinatorics of the quadratic assignment problem, Ph.D. Thesis, Universität zu Köln, 1997, 281 pp. | Zbl

[17] V. Kaibel, Extended Formulations in Combinatorial Optimization, Optima, 85, 2011, 2–7

[18] V. Kaibel, S. Weltge, “A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially”, Discrete Computational Geometry, 53:2 (2015), 396–401 | MR

[19] V. M. Kravtsov, “A characterization of the types of maximal noninteger vertices of a polyhedron in the three-index axial assignment problem”, Russian Mathematics, 50:12 (2006), 63–66 | MR

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

[21] A. N. Maksimenko, “On affine reducibility of combinatorial polytopes”, Doklady Mathematics, 85:2 (2012), 283–285 | DOI | MR | Zbl

[22] A. N. Maksimenko, “An analog of the Cook theorem for polytopes”, Russian Mathematics, 56:8 (2012), 28–34 | DOI | MR | Zbl

[23] A. N. Maksimenko, “k-Neighborly Faces of the Boolean Quadric Polytopes”, Journal of Mathematical Sciences, 203:6 (2014), 816–822 | DOI | Zbl

[24] A. N. Maksimenko, “The Common Face of some 0/1-Polytopes with NP-Complete Nonadjacency Relation”, Journal of Mathematical Sciences, 203:6 (2014), 823–832 | DOI | Zbl

[25] T. Matsui, “NP-completeness of non-adjacency relations on some 0–1-polytopes”, Lecture Notes in Operations Research, 1, 1995, 249–258

[26] M. W. Padberg, M. R. Rao, “The travelling salesman problem and a class of polyhedra of diameter two”, Math. Program., 7 (1974), 32–45 | DOI | MR | Zbl

[27] M. W. Padberg, “The Boolean quadric polytope: some characteristics, facets and relatives”, Math. Program., 45 (1989), 139–172 | DOI | MR | Zbl

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

[29] L. Qi, D. Sun, “Polyhedral Methods for Solving Three Index Assignment Problems”, Nonlinear Assignment Problems, Combinatorial Optimization, 7, eds. P. M. Pardalos, L. S. Pitsoulis, Springer, 2000, 91–107 | DOI | MR

[30] M. P. Rijal, Scheduling, design and assignment problems with quadratic costs, Ph.D. Thesis, New York University, 1995, 281 pp.

[31] H. Saito, T. Fujie, T. Matsui, Sh. Matuura, “A study of the quadratic semi-assignment polytope”, Discrete Optimization, 6:1 (2009), 37–50 | DOI | MR | Zbl

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

[33] H. P. Young, “On permutations and permutation polytopes”, Mathematical Programming Study, 8, 1978, 128–140 | DOI | MR | Zbl

[34] G. M. Ziegler, “Lectures on 0/1-Polytopes”, Polytopes — Combinatorics and Computation, DMV Seminar, 29, eds. G. Kalai, G. M. Ziegler, Birkhäuser, Basel, 2000, 1–41 | MR | Zbl