Том 21, номер 4, 2014 г., Стр. 3-11

УДК 519.2+621.391
Агеев А. А., Кельманов А. В., Пяткин А. В.
Cложность задачи о разрезе максимального веса в евклидовом пространстве

Аннотация:
Рассматривается задача поиска разреза максимального веса в полном неориентированном графе, вершинами которого являются точки q-мерного пространства. Анализируются два случая, в которых длины рёбер равны (i) евклидовым расстояниям между точками пространства и (ii) квадратам этих расстояний. Доказано, что в обоих случаях задача NP-трудна в сильном смысле. Показано также, что для них в предположении P≠NP не существует полностью полиномиальной приближённой схемы (FPTAS).
Библиогр. 17.

Ключевые слова: граф, разрез, евклидово пространство, NP-трудная задача.

Агеев Александр Александрович ¹
Кельманов Александр Васильевич ^1,2
Пяткин Артем Валерьевич ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: ageev@math.nsc.ru, kelm@math.nsc.ru, artem@math.nsc.ru

Статья поступила 3 декабря 2013 г.
Исправленный вариант — 10 февраля 2014 г.

Литература

[1] Кельманов А. В., Пяткин А. В. О сложности одного из вариантов задачи выбора подмножества «похожих» векторов // Докл. АН.-2008. - Т. 421, №5.-С. 590–592.
Kel’manov A. V., Pyatkin A. V. On the complexity of a search for a subset of “similar” vectors // Dokl. Math. - 2008. - Vol. 78, N1. - P. 574–575.

[2] Кельманов А. В., Пяткин А. В. NP-полнота некоторых задач выбора подмножества векторов // Дискрет. анализ и исслед. операций. - 2010. - Т. 17, №5. - С. 37–45.
Kel’manov A. V., Pyatkin A. V. NP-completeness of some problems of choosing a vector subset // J. Appl. Industr. Math. - 2011. - Vol. 5, N3. - P. 352–357.

[3] Кельманов А. В., Пяткин А. В. О сложности некоторых задач кластерного анализа векторных последовательностей // Дискрет. анализ и исслед. операций. - 2013. - Т. 20, №2. - С. 47–57.
Kel’manov A. V., Pyatkin A. V. On complexity of some problems of cluster analysis of vector sequences // J. Appl. Industr. Math. - 2013. - Vol. 7, N3. - P. 363–369.

[4] Barahona F., Grötschel M., Jünger M., Reinelt G. An application of combinatorial optimization to statistical physics and circuit layout design // Oper. Res. - 1988. - Vol. 36. - P. 493–513.

[5] Bern M., Eppstein D. Approximation algorithms for geometric problems // Approximation algorithms for NP-hard problems. - Boston: PWS Publ., 1997. - P. 296–345.

[6] Bui T. N., Chaudhuri S., Leighton F. T., Sipser M. Graph bisection algorithms with good average case behavior // Combinatorica. - 1987. - Vol. 7, N2. - P. 171–191.

[7] Ding C. H. Q., He X., Zha H., Gu M., Simon H. D. A min-max cut algorithm for graph partitioning and data clustering // Proc. IEEE Int. Conf. Data Mining (San Jose, Nov. 29–Dec. 2, 2001). - Los Alamitos; Washington; Brussels; Tokyo: IEEE Comput. Soc., 2001. - P. 107–114.

[8] Eisenblätter A. The semidefinite relaxation of the k-partition polytope is strong // Proc. 9th Int. IPCO Conf. Integer Programming and Combinatorial Optimization (Cambridge, MA, May 27–29, 2002). Berlin; New York: Springer-Verl., 2002. - P. 273–290. (Lect. Notes Comput. Sci.; Vol. 2337).

[9] Garey M. R., Johnson D. S. Computers and intractability: a guide to the theory of NP-completeness. - San Francisco: Freeman, 1979. - 314 p.

[10] Garey M. R., Johnson D. S., Stockmeyer L. Some simplified NP-complete graph problems // Theoret. Comput. Sci. - 1976. - Vol. 3, N1. - P. 237–267.

[11] Karp R. M. Reducibility among combinatorial problems // Complexity of computer computations. - NewYork: Plenum Press, 1972. - P. 85–103.

[12] Karp R. M. The genomics revolution and its challenges for algorithmic research // Current trends in theoretical computer science: entering the 21st century. - River Edge, NJ: World Sci. Publ. Co., Inc., 2001. - P. 631–642.

[13] Liers F., Jünger M., Reinelt G., Rinaldi G. Computing exact ground states of hard ising spin glass problems by branch-and-cut // New Optimization Algorithms in Physics. - Weinheim: Wiley-VCH Verl., 2004. - P. 47–68.

[14] Lupton R.,Maley M. P., Young N. E. Data collection for the Sloan digital sky survey: a network-flow heuristic // J. Algorithms. - 1998. - Vol. 27, N2. - P. 339–356.

[15] De Sousa S., Haxhimusa Y., Kropatsch W. G. Estimation of distribution algorithm for the Max-Cut problem // Proc. 9th IAPR-TC-15 Int.Workshop Graph-Based Representations in Pattern Recognition (Vienna, Austria, May 15–17, 2013). - Heidelberg; Dordrecht; London; New York: Springer- Verl., 2013. - P. 244–253.

[16] Vazirani V. V. Approximation algorithms. - Berlin; Heidelberg; New York: Springer-Verl., 2001. - 380 p.

[17] De la Vega F., Kenyon C. A randomized approximation scheme for metric max-cut // J. Comput. Syst. Sci. - 2001. - Vol. 63. - P. 531–541.