×

zbMATH — the first resource for mathematics

Complexity of the weighted max-cut in Euclidean space. (Russian, English) Zbl 1324.05188
Diskretn. Anal. Issled. Oper. 21, No. 4, 3-11 (2014); translation in J. Appl. Ind. Math. 8, No. 4, 453-457 (2014).
Summary: The max-cut problem is considered in an undirected graph whose vertices are points of a \(q\)-dimensional Euclidean space. The two cases are investigated, where the weights of the edges are equal to (i) the Euclidean distances between the points and (ii) the squares of these distances. It is proved that in both cases the problem is NP-hard in the strong sense. It is also shown that under the assumption \(\mathrm{P} \neq \mathrm{NP}\) there is no fully polynomial time approximation scheme (FPTAS).

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C22 Signed and weighted graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Kel’manov, A V; Pyatkin, A V, On the complexity of a search for a subset of “similar” vectors, Dokl. Ross. Akad. Nauk, 421, 590-592, (2008) · Zbl 1217.90142
[2] Kel’manov, A V; Pyatkin, A V, NP-completeness of some problems of choosing a vector subset, Diskret. Anal. Issled. Oper., 17, 37-45, (2010) · Zbl 1249.68080
[3] Kel’manov, A V; Pyatkin, A V, On complexity of some problems of cluster analysis of vector sequences, Diskret. Anal. Issled. Oper., 20, 47-57, (2013) · Zbl 1324.68047
[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., 36, 493-513, (1988) · Zbl 0646.90084
[5] Bern, M; Eppstein, D, Approximation algorithms for geometric problems, 296-345, (1997), Boston
[6] Bui, T N; Chaudhuri, S; Leighton, F T; Sipser, M, Graph bisection algorithms with good average case behavior, Combinatorica, 7, 171-191, (1987)
[7] Ding, C H Q; He, X; Zha, H; Gu, M; Simon, H D, Amin-MAX cut algorithm for graph partitioning and data clustering, 107-114, (2001), Los Alamitos
[8] Eisenblätter, A, The semidefinite relaxation of the \(k\)-partition polytope is strong, 273-290, (2002), Berlin · Zbl 1049.90136
[9] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness (Freeman, San Francisco, 1979). · Zbl 0411.68039
[10] Garey, M R; Johnson, D S; Stockmeyer, L, Some simplified NP-complete graph problems, Theor. Comput. Sci., 3, 237-267, (1976) · Zbl 0338.05120
[11] Karp, R M, Reducibility among combinatorial problems, 85-103, (1972), New York
[12] Karp, R M, The genomics revolution and its challenges for algorithmic research, 631-642, (2001), River Edge, New Jersey · Zbl 1049.68156
[13] Liers, F; Jünger, M; Reinelt, G; Rinaldi, G, Computing exact ground states of hard Ising spin Glass problems by branch-and-cut, 47-68, (2004), Weinheim · Zbl 1059.90147
[14] Lupton, R; Maley, M P; Young, N E, Data collection for the sloan digital sky survey: a network-flow heuristic, J. Algorithms, 27, 339-356, (1998) · Zbl 0905.68161
[15] Sousa, S; Haxhimusa, Y; Kropatsch, W G, Estimation of distribution algorithm for the MAX-cut problem, 244-253, (2013), Heidelberg · Zbl 1382.68235
[16] V. V. Vazirani, Approximation Algorithms (Springer, Berlin, 2001). · Zbl 0999.68546
[17] Vega, F; Kenyon, C, A randomized approximation scheme for metric MAX-cut, J. Comput. Syst. Sci., 63, 531-541, (2001) · Zbl 1006.68164
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.