Ageev, A. A.; Kel’manov, A. V.; Pyatkin, A. V. 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. Cited in 7 Documents MSC: 90C60 Abstract computational complexity for mathematical programming problems 90C27 Combinatorial optimization Keywords:Euclidean space; lengths of the edges PDFBibTeX XMLCite \textit{A. A. Ageev} et al., Dokl. Math. 89, No. 3, 343--345 (2014; Zbl 1307.90212); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 456, No. 5, 511--513 (2014) 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.