Том 23, номер 3, 2016 г., Cтр. 61–80

УДК 519.854
Максименко А. Н.
Сложность задач комбинаторной оптимизации в терминах решёток граней ассоциированных многогранников

Аннотация:
Основной мотивацией работы является следующий вопрос, связанный со свойствами многогранников, ассоциированных с задачами комбинаторной оптимизации. Можно ли, зная комбинаторные свойства многогранника, оценить сложность соответствующей оптимизационной задачи? В разное время в качестве таких ключевых характеристик сложности рассматривались число гиперграней многогранника, диаметр и кликовое число его графа, число прямоугольного покрытия матрицы инциденций вершин-гиперграней и некоторые другие. В настоящей работе приводится несколько примеров семейств многогранников, для которых значения упомянутых выше характеристик существенно отличаются от реальной вычислительной сложности соответствующих оптимизационных задач. В частности, приводятся примеры двух задач дискретной оптимизации, многогранники которых комбинаторно эквивалентны и длины двоичной записи координат вершин этих многогранников одинаковы. При этом первая задача разрешима за полиномиальное время, а вторая задача имеет экспоненциальную сложность.
Ил. 1, библиогр. 22.

Ключевые слова: NP-трудная задача, матрица инциденций вершин-гиперграней, комбинаторная эквивалентность, граф многогранника, кликовое число графа, расширенная формулировка, циклический многогранник.

DOI: 10.17377/daio.2016.23.515

Максименко Александр Николаевич ¹
1. Ярославский гос. университет им. П. Г. Демидова,
ул. Советская, 14, 150000 Ярославль, Россия
е-mail: maximenko.a.n@gmail.com

Статья поступила 13 октября 2015 г.
Исправленный вариант — 19 апреля 2016 г.

Литература

[1] Бондаренко В. А., Максименко А. Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 c.

[2] Бондаренко В. А., Николаев А. В. Комбинаторно-геометрические свойства задачи о разрезе // Докл. АН. 2013. Т. 452, № 2. С. 127–129.

[3] Деза M. M., Лоран M. Геометрия разрезов и метрик. М: МЦНМО, 2001. 736 с.

[4] Максименко А. Н. Общая грань некоторых 0/1-многогранников с NP-полным критерием несмежности вершин // Фундамент. и прикл. математика. 2013. Т. 18, № 2. С. 105–118.

[5] Максименко А. Н. Характеристики сложности: кликовое число графа многогранника и число прямоугольного покрытия // Модел. и анализ информ. систем. 2014. Т. 21, № 5. С. 116–130

[6] Максименко А. Н. Наиболее простые семейства многогранников, ассоциированных с NP-трудными задачами // Докл. АН. 2015. Т. 460, № 3. С. 272–274.

[7] Циглер Г. М. Теория многогранников. М.: МЦНМО, 2014. 568 c.

[8] Applegate D. L., Bixby R. M., Chvátal V., Cook W. J. The traveling salesman problem: a computational study. Princeton: Princeton Univ. Press, 2007. 608 p.

[9] Bogomolov Yu., Fiorini S., Maksimenko A., Pashkovich K. Small extended formulations for cyclic polytopes // Discrete Comput. Geom. 2015. Vol. 53, No. 4. P. 809–816.

[10] Conforti M., Cornuéjols G., Zambelli G. Extended formulations in combinatorial optimization // Ann. Oper. Res. 2013. Vol. 204, No. 1. P. 97–143.

[11] Dantzig G. B., Fulkerson D. R., Johnson S. M. Solution of a large-scale traveling salesman problem // Oper. Res. 1954. Vol. 2, No. 4. P. 393–410.

[12] Fiorini S., Kaibel V., Pashkovich K., Theis D. O. Combinatorial bounds on nonnegative rank and extended formulations // Discrete Math. 2013. Vol. 313, No. 1. P. 67–83.

[13] Fiorini S., Massar S., Pokutta S., Tiwary H. R., de Wolf R. Exponential lower bounds for polytopes in combinatorial optimization // J. ACM. 2015. Vol. 62, No. 2. P. 17:1–17:23.

[14] Fiorini S., Rothvoß T., Tiwary H. R. Extended formulations for polygons // Discrete Comput. Geom. 2012. Vol. 48, No. 13. P. 658–668.

[15] Grünbaum B. Convex polytopes. New York: Springer-Verl., 2003. 471 p.

[16] Kaibel V. Extended formulations in combinatorial optimization // Optima 85, Math. Optim. Soc. Newsl. No. 85. 2011. P. 2–7.

[17] Kaibel V., Pfetsch M. E. Computing the face lattice of a polytope from its vertex-facet incidences // Comput. Geom. 2002. Vol. 23, No. 3. P. 281–290.

[18] Kaibel V., Weltge S. A short proof that the extension complexity of the correlation polytope grows exponentially // Discrete Comput. Geom. 2015. Vol. 53, No. 2. P. 397–401.

[19] Padberg M. W., Rao M. R. The travelling salesman problem and a class of polyhedra of diameter two // Math. Program. 1974. Vol. 7. P. 32–45.

[20] Rothvoß T. The matching polytope has exponential extension complexity // Proc. 46th Annu. ACM Symp. Theory Comput. (New York, May 31–June 3, 2014). New York: ACM, 2014. P. 263–272.

[21] Shannon C. Communication theory of secrecy systems // Bell System Techn. J. 1949. Vol. 28, No. 4. P. 656–715.

[22] Yannakakis M. Expressing combinatorial optimization problems by linear programs // J. Comput. Syst. Sci. 1991. Vol. 43, No. 3. P. 441–466.