Характеристики сложности: кликовое число графа многогранника и число прямоугольного покрытия


https://doi.org/10.18255/1818-1015-2014-5-116-130

Полный текст:


Аннотация

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


Об авторе

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


Список литературы

1. Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. Ярославль: ЯрГУ, 1995. [Bondarenko V.A. Poliedralnye grafy i slozhnost v kombinatornoy optimizatsii. Yaroslavl: YarGU, 1995 (in Russian)].

2. Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. M.: ЛКИ, 2008. [Bondarenko V.A., Maksimenko A.N. Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moskva: LKI, 2008 (in Russian)].

3. Бондаренко В.А., Николаев А.В. Комбинаторно-геометрические свойства задачи о разрезе // Доклады Академии наук. Математика. 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.)

4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 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.)

5. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 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.)

6. Колесов Е.В., Максименко А.Н. Анализ одного алгоритма для задачи о назначениях // Заметки по информатике и математике. Ярославль: ЯрГУ, 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)].

7. Максименко А.Н. Комбинаторные свойства многогранника задачи о кратчайшем пути // Журнал вычислительной математики и математической физики. 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.)

8. Максименко А.Н. 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)].

9. Мошков М.Ю. Об условных тестах // Доклады АН СССР. 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.)

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

11. 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.

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

13. 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.

14. 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.

15. Gaiha P., Gupta S.K. Adjacent vertices on a permutohedron // SIAM Journal on Applied Mathematics. 1977. V. 32, No 2. P. 323–327.

16. Kaibel V. Extended Formulations in Combinatorial Optimization // Optima. 2011. 85.

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

18. Maksimenko A.N. A special place of Boolean quadratic polytopes among other combinatorial polytopes // arXiv:1408.0948

19. Rothvoss T. The matching polytope has exponential extension complexity // STOC. 2014. P. 263–272.

20. Yannakakis M. Expressing combinatorial optimization problems by linear programs // J. Comput. System Sci. 1991. V. 43, No 3. P. 441–466.


Дополнительные файлы

Для цитирования: Максименко А.Н. Характеристики сложности: кликовое число графа многогранника и число прямоугольного покрытия. Моделирование и анализ информационных систем. 2014;21(5):116-130. https://doi.org/10.18255/1818-1015-2014-5-116-130

For citation: Maksimenko A.N. Characteristics of Complexity: Clique Number of a Polytope Graph and Rectangle Covering Number. Modeling and Analysis of Information Systems. 2014;21(5):116-130. (In Russ.) https://doi.org/10.18255/1818-1015-2014-5-116-130

Просмотров: 253

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)