Volume 21, No 4, 2014, P. 311
UDC 519.2+621.391
A. A. Ageev, A. V. Kel’manov and A. V. Pyatkin
Complexity of the euclidean max cut problem
Abstract:
We consider the following problem: given a complete edgeweighted undirected graph whose vertices are points of a qdimensional 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 NPhard do no permit FPTAS unless P≠NP.
Bibliogr. 17.
Keywords: graph, cut, Euclidean space, NPhard problem.
Ageev Alexander Alexandrovich ^{1}
Kel’manov Alexander Vasilievich ^{1,2}
Pyatkin Artem Valerievich ^{1,2}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
email: ageev@math.nsc.ru, kelm@math.nsc.ru, artem@math.nsc.ru
