Complexity of the weighted max-cut in Euclidean space
Alexander A. Ageev, Alexander V. Kel’manov, A. V. Pyatkin · Journal of Applied and Industrial Mathematics · 2014
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 P≠=NP there is no fully polynomial time approximation scheme (FPTAS).