×

NP-hardness of the Euclidean Max-Cut problem. (English. Russian original) Zbl 1307.90212

Dokl. Math. 89, No. 3, 343-345 (2014); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 456, No. 5, 511-513 (2014).
Summary: We study the computational complexity of the Max-Cut problem in two geometric cases. In both cases, the graph vertices are defined by points of Euclidean space, and the lengths of the edges are given by either distances (Euclidean Max-Cut) or squared distances (quadratic Euclidean Max-Cut) between these points. The dimension of the space is assumed to be part of the input to the problem.

MSC:

90C60 Abstract computational complexity for mathematical programming problems
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barahona, F.; Grötschel, M.; Jünger, M.; Reinelt, G., No article title, Oper. Res., 36, 493-513 (1988) · Zbl 0646.90084 · doi:10.1287/opre.36.3.493
[2] M. Bern and D. Eppstein, in Approximation Algorithms for NP-Hard Problems (PWS Boston, 1997), pp. 296-345.
[3] Bui, T. N.; Chaudhuri, S.; Leighton, F. T.; Sipser, M., No article title, Combinatorica, 7, 171-191 (1987) · doi:10.1007/BF02579448
[4] C. H. Q. Ding, He Xiaofeng, Zha Hongyuan, Gu Ming, H. D. Simon, in Proceedings of IEEE Inter-national Conference on Data Mining, San Jose, California, Nov. 29-Dec. 2, 2001 (IEEE Comput. Soc., Los Alamitos (CA), 2001), pp. 107-114. · doi:10.1109/ICDM.2001.989507
[5] A. Eisenblätter, in Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, Cambridge (MA), May 27-29, 2002 (Springer, Berlin, 2002), Lect. Notes Comput. Sci. 2337, 273-290 (2002).
[6] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). · Zbl 0411.68039
[7] Garey, M. R.; Johnson, D. S.; Stockmeyer, L., No article title, Theor. Comput. Sci., 3, 237-267 (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[8] R. M. Karp, in Complexity of Computer Computations (Plenum, New York, 1972), pp. 85-103. · doi:10.1007/978-1-4684-2001-2_9
[9] R. M. Karp, in Current Trends in Theoretical Computer Science: Entering the 21st Century (World Scientific, River Edge (NJ), 2001), pp. 631-642.
[10] F. Liers, M. Jünger, G. Reinelt, and G. Rinaldi, in New Optimization Algorithms in Physics (Wiley-VCH, Weinheim, 2004), pp. 47-68.
[11] Lupton, R.; Maley, M. P.; Young, N. E., No article title, J. Algorithms, 27, 339-356 (1998) · Zbl 0905.68161 · doi:10.1006/jagm.1997.0922
[12] S. de Sousa, Y. Haxhimusa, and W. G. Kropatsch, in Proceedings of the 9th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, Vienna, May 15-17, 2013 (Springer, Heidelberg, 2013), pp. 244-253. · Zbl 1382.68235
[13] Vega, F.; Kenyon, C., No article title, J. Comput. Syst. Sci., 63, 531-541 (2001) · Zbl 1006.68164 · doi:10.1006/jcss.2001.1772
[14] Kel’manov, A. V.; Pyatkin, A. V., No article title, Dokl. Math., 78, 574-575 (2008) · Zbl 1217.90142 · doi:10.1134/S1064562408040273
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.