Geodesic
Complexity of the Euclidean max cut problem
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 4, pp. 3-11.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the following problem: given a complete edge-weighted undirected graph whose vertices are points of a $q$-dimensional space, find a cut of maximum total weight. Two special cases are analyzed where the edge weights are equal to (i) the Euclidean distances between points representing the vertices, (ii) the squares of these distances. We prove that both cases of the problem are strongly NP-hard do no permit FPTAS unless $\mathrm{P\neq NP}$. Bibliogr. 17.
Keywords: graph, cut, Euclidean space, NP-hard problem. 
@article{DA_2014_21_4_a0,
     author = {A. A. Ageev and A. V. Kel'manov and A. V. Pyatkin},
     title = {Complexity of the {Euclidean} max cut problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--11},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_4_a0/}
}
TY  - JOUR
AU  - A. A. Ageev
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
TI  - Complexity of the Euclidean max cut problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 3
EP  - 11
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_4_a0/
LA  - ru
ID  - DA_2014_21_4_a0
ER  - 
%0 Journal Article
%A A. A. Ageev
%A A. V. Kel'manov
%A A. V. Pyatkin
%T Complexity of the Euclidean max cut problem
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 3-11
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_4_a0/
%G ru
%F DA_2014_21_4_a0
A. A. Ageev; A. V. Kel'manov; A. V. Pyatkin. Complexity of the Euclidean max cut problem. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 4, pp. 3-11. http://geodesic.mathdoc.fr/item/DA_2014_21_4_a0/

[1] Kel'manov A. V., Pyatkin A. V., “On the complexity of a search for a subset of “similar” vectors”, Dokl. Math., 78:1 (2008), 574–575 | DOI | MR

[2] Kel'manov A. V., Pyatkin A. V., “NP-completeness of some problems of choosing a vector subset”, J. Appl. Industr. Math., 5:3 (2011), 352–357 | DOI | MR | Zbl

[3] Kel'manov A. V., Pyatkin A. V., “On complexity of some problems of cluster analysis of vector sequences”, J. Appl. Industr. Math., 7:3 (2013), 363–369 | DOI | MR

[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 (1988), 493–513 | DOI | Zbl

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

[6] Bui T. N., Chaudhuri S., Leighton F. T., Sipser M., “Graph bisection algorithms with good average case behavior”, Combinatorica, 7:2 (1987), 171–191 | DOI | MR

[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), IEEE Comput. Soc., Los Alamitos–Washington–Brussels–Tokyo, 2001, 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), Lect. Notes Comput. Sci., 2337, Springer-Verl., Berlin–New York, 2002, 273–290 | DOI | MR | Zbl

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

[10] Garey M. R., Johnson D. S., Stockmeyer L., “Some simplified NP-complete graph problems”, Theoret. Comput. Sci., 3:1 (1976), 237–267 | DOI | MR

[11] Karp R. M., “Reducibility among combinatorial problems”, Complexity of computer computations, Plenum Press, New York, 1972, 85–103 | DOI | MR

[12] Karp R. M., “The genomics revolution and its challenges for algorithmic research”, Current trends in theoretical computer science, Entering the 21st century, World Sci. Publ. Co., Inc., River Edge, NJ, 2001, 631–642 | MR | Zbl

[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, Wiley-VCH Verl., Weinheim, 2004, 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, 27:2 (1998), 339–356 | DOI | MR | Zbl

[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), Springer-Verl., Heidelberg–Dordrecht–London–New York, 2013, 244–253 | DOI | MR | Zbl

[16] Vazirani V. V., Approximation algorithms, Springer-Verl., Berlin–Heidelberg–New York, 2001, 380 pp. | MR

[17] De la Vega F., Kenyon C., “A randomized approximation scheme for metric max-cut”, J. Comput. Syst. Sci., 63 (2001), 531–541 | DOI | MR | Zbl