An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes |
| |
Authors: | Refael Hassin Shlomi Rubinstein |
| |
Affiliation: | Department of Statistics and Operations Research, School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel |
| |
Abstract: | The input to the metric maximum clustering problem with given cluster sizes consists of a complete graph G=(V,E) with edge weights satisfying the triangle inequality, and integers c1,…,cp. The goal is to find a partition of V into disjoint clusters of sizes c1,…,cp, maximizing the sum of weights of edges whose two ends belong to the same cluster. We describe an approximation algorithms for this problem with performance guarantee that approaches 0.5 when the cluster sizes are large. |
| |
Keywords: | Approximation algorithms Maximum weight clustering |
本文献已被 ScienceDirect 等数据库收录! |
|