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/