Approximation algorithms for min-sum <i>p</i>-clustering

作     者：Guttmann-Beck, N Hassin, R 

作者机构：Tel Aviv Univ Dept Stat & Operat Res IL-69978 Tel Aviv Israel 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：1998年第89卷第1-3期

页      面：125-142页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：approximation algorithm p-clustering 

摘      要：We consider the following problem: Given a graph with edge lengths satisfying the triangle inequality, partition its node set into p subsets, minimizing the total length of edges whose two ends are in the same subset. For this problem we present an approximation algorithm which comes to at most twice the optimal value. For clustering into two equal-sized sets, the exact bound on the maximum possible error ratio of our algorithm is between 1.686 and 1.7. (C) 1998 Elsevier Science B.V. All rights reserved.