未找到相关数据
A randomized approximation scheme for metric MAX-CUT
被引：11
作者：
de la Vega, WF
[1
]
Kenyon, C
[1
]
机构：
[1] Univ Paris Sud, CNRS, LRI, F-91405 Orsay, France
来源：
39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS
|
1998年
关键词：
D O I：
10.1109/SFCS.1998.743497
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ;
0812 ;
0835 ;
1405 ;
摘要：
Metric MAX-CUT is the problem of dividing a set of paints in metric space into two parts so as to maximize the sum of the distances between points belonging to distinct parts. We show that metric MAX-CUT has a polynomial time randomized approximation scheme.
引用
收藏
页码：468 / 471
页数：2
相关论文