maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2014-5-116-130mais-89Research ArticleОригинальные статьиArticlesХарактеристики сложности: кликовое число графа многогранника и число прямоугольного покрытияCharacteristics of Complexity: Clique Number of a Polytope Graph and Rectangle Covering NumberМаксименкоАлександр НиколаевичMaksimenkoA. N.

канд. физ.-мат. наук, науч. сотр. лаборатории «Дискретная и вычислительная геометрия» им. Б. Н. Делоне, 150000 Россия, г. Ярославль, ул. Советская, 14

канд. физ.-мат. наук, науч. сотр. лаборатории «Дискретная и вычислительная геометрия» им. Б. Н. Делоне, Sovetskaya str., 14, Yaroslavl, 150000, Russia

maximenko.a.n@gmail.comЯрославский государственный университет им. П. Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation201420102014215116130Copyright © Максименко А.Н., 20142014Максименко А.Н.Maksimenko A.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/89

В 1980-х гг. В.А. Бондаренко обнаружил, что кликовое число графа многогранника во многих случаях соответствует реальной сложности задачи оптимизации на вершинах этого многогранника. Для объяснения этого феномена была предложена теория алгоритмов прямого типа, утверждающая, что кликовое число графа многогранника является нижней оценкой сложности соответствующей задачи в так называемом классе алгоритмов прямого типа. Более того, утверждалось, что этот класс является достаточно широким, включающим в себя многие классические комбинаторные алгоритмы. В настоящей работе приводится несколько примеров, призванных обозначить границы применимости этой теории. В частности, описана довольно часто используемая на практике модификация алгоритмов, выводящая их из указанного класса (порядок трудоемкости при этом не меняется). Другой, значительно более близкой к реальности, комбинаторной характеристикой сложности является число прямоугольного покрытия матрицы инциденций фасет-вершин, введенное в рассмотрение М. Яннакакисом в 1988 г. Мы приводим пример многогранника с полиномиальным (относительно размерности многогранника) значением этой характеристики, задача оптимизации на вершинах которого NP-трудна.

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.

комбинаторная оптимизациявыпуклые многогранникисложность задач и алгоритмовграф многогранникакликовое числорасширенные формулировкиматрица инциденций фасет-вершинчисло прямоугольного покрытияcombinatorial optimizationconvex polytopescomplexity of problems and algorithms1-skeleton of a polytopeclique numberextended formulationsfacet-vertex incidence matrixrectangle covering numberпроект №477 в рамках базовой части государственного задания на НИР ЯрГУReferencesБондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. Ярославль: ЯрГУ, 1995. [Bondarenko V.A. Poliedralnye grafy i slozhnost v kombinatornoy optimizatsii. Yaroslavl: YarGU, 1995 (in Russian)].Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. Ярославль: ЯрГУ, 1995. [Bondarenko V.A. Poliedralnye grafy i slozhnost v kombinatornoy optimizatsii. Yaroslavl: YarGU, 1995 (in Russian)].Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. M.: ЛКИ, 2008. [Bondarenko V.A., Maksimenko A.N. Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moskva: LKI, 2008 (in Russian)].Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. M.: ЛКИ, 2008. [Bondarenko V.A., Maksimenko A.N. Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moskva: LKI, 2008 (in Russian)].Бондаренко В.А., Николаев А.В. Комбинаторно-геометрические свойства задачи о разрезе // Доклады Академии наук. Математика. 2013. Т. 452, № 2. С. 127–129. (English transl.: Bondarenko V.A., Nikolaev A.V. Combinatorial and Geometric Properties of the Max-Cut and Min-Cut Problems // Doklady Mathematics. 2013. V. 88, No 2. P. 516–517.)Бондаренко В.А., Николаев А.В. Комбинаторно-геометрические свойства задачи о разрезе // Доклады Академии наук. Математика. 2013. Т. 452, № 2. С. 127–129. (English transl.: Bondarenko V.A., Nikolaev A.V. Combinatorial and Geometric Properties of the Max-Cut and Min-Cut Problems // Doklady Mathematics. 2013. V. 88, No 2. P. 516–517.)Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. (Garey M.R. and Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co., 1979.)Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. (Garey M.R. and Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co., 1979.)Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. (English transl.: Yemelichev V.A., Kovalev M.M., Kravtsov M.K. Polytopes, Graphs and Optimisation; translated by G.H. Lawden. Cambridge: Cambridge Univ. Press, 1984.)Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. (English transl.: Yemelichev V.A., Kovalev M.M., Kravtsov M.K. Polytopes, Graphs and Optimisation; translated by G.H. Lawden. Cambridge: Cambridge Univ. Press, 1984.)Колесов Е.В., Максименко А.Н. Анализ одного алгоритма для задачи о назначениях // Заметки по информатике и математике. Ярославль: ЯрГУ, 2009. Вып. 1. С. 36–40. [Kolesov E.V., Maksimenko A.N. Analiz odnogo algoritma dlya zadachi o naznacheniyakh // Zametki po informatike i matematike. Yaroslavl: YarGU, 2009. Vyp. 1. S. 36–40 (in Russian)].Колесов Е.В., Максименко А.Н. Анализ одного алгоритма для задачи о назначениях // Заметки по информатике и математике. Ярославль: ЯрГУ, 2009. Вып. 1. С. 36–40. [Kolesov E.V., Maksimenko A.N. Analiz odnogo algoritma dlya zadachi o naznacheniyakh // Zametki po informatike i matematike. Yaroslavl: YarGU, 2009. Vyp. 1. S. 36–40 (in Russian)].Максименко А.Н. Комбинаторные свойства многогранника задачи о кратчайшем пути // Журнал вычислительной математики и математической физики. 2004. Т. 44. № 9. С. 1693–1696. (English transl.: Maksimenko A.N. Combinatorial properties of the polyhedron of the shortest path problem // Comput. Math. Math. Phys. 2004. V. 44, No. 9, P. 1611–1614.)Максименко А.Н. Комбинаторные свойства многогранника задачи о кратчайшем пути // Журнал вычислительной математики и математической физики. 2004. Т. 44. № 9. С. 1693–1696. (English transl.: Maksimenko A.N. Combinatorial properties of the polyhedron of the shortest path problem // Comput. Math. Math. Phys. 2004. V. 44, No. 9, P. 1611–1614.)Максименко А.Н. k-смежностные грани булева квадратичного многогранника // Фундаментальная и прикладная математика. 2013. Т. 18, № 2. С. 95—103. [Maksimenko A.N. k-smezhnostnye grani buleva kvadratichnogo mnogogrannika // Fundamentalnaya i prikladnaya matematika. 2013. T. 18, № 2. S. 95—103 (in Russian)].Максименко А.Н. k-смежностные грани булева квадратичного многогранника // Фундаментальная и прикладная математика. 2013. Т. 18, № 2. С. 95—103. [Maksimenko A.N. k-smezhnostnye grani buleva kvadratichnogo mnogogrannika // Fundamentalnaya i prikladnaya matematika. 2013. T. 18, № 2. S. 95—103 (in Russian)].Мошков М.Ю. Об условных тестах // Доклады АН СССР. 1982. Т. 265, № 3. С. 550–552. (English transl.: Moshkov M.Ju. On conditional tests // Academy of Sciences Doklady. 1982. V. 265, No 3. P. 550–552.)Мошков М.Ю. Об условных тестах // Доклады АН СССР. 1982. Т. 265, № 3. С. 550–552. (English transl.: Moshkov M.Ju. On conditional tests // Academy of Sciences Doklady. 1982. V. 265, No 3. P. 550–552.)Bogomolov Yu., Fiorini S., Maksimenko A., Pashkovich K. Small Extended Formulations for Cyclic Polytopes // arXiv:1401.8138Bogomolov Yu., Fiorini S., Maksimenko A., Pashkovich K. Small Extended Formulations for Cyclic Polytopes // arXiv:1401.8138Conforti M., Cornu´ejols G., and Zambelli G. Extended formulations in combinatorial optimization // A Quarterly Journal of Operations Research. 2010. V. 8, No 1. P. 1–48.Conforti M., Cornu´ejols G., and Zambelli G. Extended formulations in combinatorial optimization // A Quarterly Journal of Operations Research. 2010. V. 8, No 1. P. 1–48.Deza M.M., Laurent M. Geometry of cuts and metrics. Springer, 1997.Deza M.M., Laurent M. Geometry of cuts and metrics. Springer, 1997.Fiorini S., Massar S., Pokutta S., Tiwary H.R., de Wolf R. Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds // STOC. 2012. P. 95–106.Fiorini S., Massar S., Pokutta S., Tiwary H.R., de Wolf R. Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds // STOC. 2012. P. 95–106.Fiorini S., Kaibel V., Pashkovich K., Theis D.O. Combinatorial Bounds on Nonnegative Rank and Extended Formulations // Discrete Math. 2013. V. 313, No 1. P. 67–83.Fiorini S., Kaibel V., Pashkovich K., Theis D.O. Combinatorial Bounds on Nonnegative Rank and Extended Formulations // Discrete Math. 2013. V. 313, No 1. P. 67–83.Gaiha P., Gupta S.K. Adjacent vertices on a permutohedron // SIAM Journal on Applied Mathematics. 1977. V. 32, No 2. P. 323–327.Gaiha P., Gupta S.K. Adjacent vertices on a permutohedron // SIAM Journal on Applied Mathematics. 1977. V. 32, No 2. P. 323–327.Kaibel V. Extended Formulations in Combinatorial Optimization // Optima. 2011. 85.Kaibel V. Extended Formulations in Combinatorial Optimization // Optima. 2011. 85.Kaibel V., Weltge S. A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially // arXiv:1307.3543, 2013.Kaibel V., Weltge S. A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially // arXiv:1307.3543, 2013.Maksimenko A.N. A special place of Boolean quadratic polytopes among other combinatorial polytopes // arXiv:1408.0948Maksimenko A.N. A special place of Boolean quadratic polytopes among other combinatorial polytopes // arXiv:1408.0948Rothvoss T. The matching polytope has exponential extension complexity // STOC. 2014. P. 263–272.Rothvoss T. The matching polytope has exponential extension complexity // STOC. 2014. P. 263–272.Yannakakis M. Expressing combinatorial optimization problems by linear programs // J. Comput. System Sci. 1991. V. 43, No 3. P. 441–466.Yannakakis M. Expressing combinatorial optimization problems by linear programs // J. Comput. System Sci. 1991. V. 43, No 3. P. 441–466.

The authors declare that there are no conflicts of interest present.