A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes


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


Рассматриваются несколько семейств комбинаторных многогранников, ассоциированных со следующими NP-полными задачами: максимальный разрез, булево квадратичное программирование, квадратичная задача линейного упорядочения, квадратичные назначения, разбиение и упаковка множества, независимое множество, 3-назначения. Для сравнения двух семейств многогранников используется следующий способ. Будем говорить, что семейство

Об авторе

Александр Николаевич Максименко
Ярославский государственный университет им. П.Г. Демидова
канд. физ.-мат. наук, доцент

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

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

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

3. L. J. Billera, A. Sarangarajan, “All 0-1 polytopes are travelling salesman polytopes”, Combinatorica, 16:2 (1996), 175–188.

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

5. C. Buchheim, A. Wiegele, and L. Zheng, “Exact Algorithms for the Quadratic Linear Ordering Problem”, INFORMS J. on Computing, 22:1 (2010), 168–177.

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

7. M. Conforti, G. Cornu´ejols, and G. Zambelli, “Extended formulations in combinatorial optimization”, A Quarterly Journal of Operations Research, 8:1 (2010), 1–48.

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

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

10. M. M. Deza, M. Laurent, Geometry of cuts and metrics, Springer, 1997, 588 pp.

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.

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

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.

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

15. M. Gr¨otschel, M. J¨unger, and G. Reinelt, “Facets of the linear ordering polytope”, Math. Program., 33 (1985), 43–60.

16. V. Kaibel, Polyhedral combinatorics of the quadratic assignment problem, Ph.D. Thesis, Universit¨at zu K¨oln, 1997, 281 pp.

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.

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.

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

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

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

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

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.

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 and M. R. Rao, “The travelling salesman problem and a class of polyhedra of diameter two”, Math. Program., 7 (1974), 32–45.

27. M. W. Padberg, “The boolean quadric polytope: some characteristics, facets and relatives”, Math. Program., 45 (1989), 139–172.

28. C. H. Papadimitriou, “The adjacency relation on the traveling salesman polytope is NPcomplete”, Math. Program., 14:1 (1978), 312–324.

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

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.

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

33. H.P. Young, “On permutations and permutation polytopes”, Mathematical Programming Study, 8 (1978), 128–140.

34. G. M. Ziegler, “Lectures on 0/1-Polytopes”, Polytopes — Combinatorics and Computation, DMV Seminar, 29, eds. G. Kalai and G. M. Ziegler, Birkh¨auser Basel, 2000, 1–41.

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

Для цитирования: Максименко А.Н. A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes. Моделирование и анализ информационных систем. 2016;23(1):23-40. https://doi.org/10.18255/1818-1015-2016-1-23-40

For citation: Maksimenko A.N. A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes. Modeling and Analysis of Information Systems. 2016;23(1):23-40. (In Russ.) https://doi.org/10.18255/1818-1015-2016-1-23-40

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

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

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

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

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