Geodesic
Characteristics of complexity: clique number of a polytope graph and rectangle covering number
Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 5, pp. 116-130.

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

In the 1980s V A. Bondarenko found that the clique number of the graph of a polytope in many cases corresponds to the actual complexity of the optimization problem on the vertices of the polytope. For an explanation of this phenomenon he proposed the theory of direct type algorithms. This theory asserts that the clique number of the graph of a polytope is the lower bound of the complexity of the corresponding problem in the so-called class of direct type algorithms. Moreover, it was argued that this class is wide enough and includes many classical combinatorial algorithms. In this paper we present a few examples, designed to identify the limits of applicability of this theory. In particular, we describe a modification of algorithms that is quite frequently used in practice. This modification takes the algorithms out of the specified class, while the complexity is not changed. Another, much closer to reality combinatorial characteristic of complexity is the rectangle covering number of the facet-vertex incidence matrix, introduced into consideration by M. Yannakakis in 1988. We give an example of a polytope with a polynomial (with respect to the dimension of the polytope) value of this characteristic, while the corresponding optimization problem is NP-hard.
Keywords: combinatorial optimization, convex polytopes, complexity of problems and algorithms, 1-skeleton of a polytope, clique number, extended formulations, rectangle covering number.
Mots-clés : facet-vertex incidence matrix 
@article{MAIS_2014_21_5_a7,
     author = {A. N. Maksimenko},
     title = {Characteristics of complexity: clique number of a polytope graph and rectangle covering number},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {116--130},
     publisher = {mathdoc},
     volume = {21},
     number = {5},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2014_21_5_a7/}
}
TY  - JOUR
AU  - A. N. Maksimenko
TI  - Characteristics of complexity: clique number of a polytope graph and rectangle covering number
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2014
SP  - 116
EP  - 130
VL  - 21
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2014_21_5_a7/
LA  - ru
ID  - MAIS_2014_21_5_a7
ER  - 
%0 Journal Article
%A A. N. Maksimenko
%T Characteristics of complexity: clique number of a polytope graph and rectangle covering number
%J Modelirovanie i analiz informacionnyh sistem
%D 2014
%P 116-130
%V 21
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2014_21_5_a7/
%G ru
%F MAIS_2014_21_5_a7
A. N. Maksimenko. Characteristics of complexity: clique number of a polytope graph and rectangle covering number. Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 5, pp. 116-130. http://geodesic.mathdoc.fr/item/MAIS_2014_21_5_a7/

[1] Bondarenko V. A., Poliedralnye grafy i slozhnost v kombinatornoy optimizatsii, YarGU, Yaroslavl, 1995

[2] Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii, LKI, Moskva, 2008

[3] V. A. Bondarenko, A. V. Nikolaev, “Combinatorial and Geometric Properties of the Max-Cut and Min-Cut Problems”, Doklady Mathematics, 88:2 (2013), 516–517

[4] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979

[5] V. A. Yemelichev, M. M. Kovalev, M. K. Kravtsov, Polytopes, Graphs and Optimisation, translated by G.H. Lawden, Cambridge Univ. Press, Cambridge, 1984

[6] Kolesov E. V., Maksimenko A. N., “Analiz odnogo algoritma dlya zadachi o naznacheniyakh”, Zametki po informatike i matematike, 1 (2009), 36–40, YarGU, Yaroslavl

[7] A. N. Maksimenko, “Combinatorial properties of the polyhedron of the shortest path problem”, Comput. Math. Math. Phys., 44:9 (2004), 1611–1614

[8] Maksimenko A. N., “k-smezhnostnye grani buleva kvadratichnogo mnogogrannika”, Fundamentalnaya i prikladnaya matematika, 18:2 (2013), 95–103

[9] M. Ju. Moshkov, “On conditional tests”, Academy of Sciences Doklady, 265:3 (1982), 550–552

[10] Yu. Bogomolov, S. Fiorini, A. Maksimenko, K. Pashkovich, “Small Extended Formulations for Cyclic Polytopes”, arXiv: 1401.8138

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

[12] M. M. Deza, M. Laurent, Geometry of cuts and metrics, Springer, 1997

[13] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, “Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds”, STOC, 2012, 95–106

[14] S. Fiorini, V. Kaibel, K. Pashkovich, D. O. Theis, “Combinatorial Bounds on Nonnegative Rank and Extended Formulations”, Discrete Math., 313:1 (2013), 67–83

[15] P. Gaiha, S. K. Gupta, “Adjacent vertices on a permutohedron”, SIAM Journal on Applied Mathematics, 32:2 (1977), 323–327

[16] V. Kaibel, “Extended Formulations in Combinatorial Optimization”, Optima, 85 (2011)

[17] V. Kaibel, S. Weltge, “A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially”, 2013, arXiv: 1307.3543

[18] A. N. Maksimenko, “A special place of Boolean quadratic polytopes among other combinatorial polytopes”, arXiv: 1408.0948

[19] T. Rothvoss, “The matching polytope has exponential extension complexity”, STOC, 2014, 263–272

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