Complexity of the weighted max-cut in Euclidean space

被引：0

作者：

Ageev A.A. ^{[1
]}

Kel’manov A.V. ^{[1
,2
]}

Pyatkin A.V. ^{[1
,2
]}

机构：

[1] Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk

[2] Novosibirsk State University, ul. Pirogova 2, Novosibirsk

来源：

Journal of Applied and Industrial Mathematics | 2014年 / 8卷 / 04期

基金：

俄罗斯基础研究基金会;

关键词：

cut; Euclidean space; graph; NP-hard problem;

D O I：

10.1134/S1990478914040012

中图分类号：

学科分类号：

摘要：

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). © 2014, Pleiades Publishing, Ltd.

引用

页码：453 / 457

页数：4

共 17 条

[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, 5, pp. 590-592, (2008)

[2]

Kel'manov A.V., Pyatkin A.V., NP-Completeness of Some Problems of Choosing a Vector Subset, Diskret. Anal. Issled. Oper., 17, 5, pp. 37-45, (2010)

[3]

Kel'manov A.V., Pyatkin A.V., On Complexity of Some Problems of Cluster Analysis of Vector Sequences, Diskret. Anal. Issled. Oper., 20, 2, pp. 47-57, (2013)

[4]

Barahona F., Grotschel M., Junger M., Reinelt G., An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design, Oper. Res., 36, pp. 493-513, (1988)

[5]

Bern M., Eppstein D., Approximation Algorithms for Geometric Problems, Approximation Algorithms for NP Hard Problems, pp. 296-345, (1997)

[6]

Bui T.N., Chaudhuri S., Leighton F.T., Sipser M., Graph Bisection Algorithms with Good Average Case Behavior, Combinatorica, 7, 2, pp. 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, Proceedings of IEEE International Conference on Data Mining (San Jose, November 29–December 2, 2001), pp. 107-114, (2001)

[8]

Eisenblatter A., The Semidefinite Relaxation of the k-Partition Polytope is Strong, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization (Cambridge, MA, May 27–29, 2002), pp. 273-290, (2002)

[9]

Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NPCompleteness, (1979)

[10]

Garey M.R., Johnson D.S., Stockmeyer L., Some Simplified NP-Complete Graph Problems, Theor. Comput. Sci., 3, 1, pp. 237-267, (1976)

← 1 2 →