Balcan2009

CREATED: 201005191558 TITLE: Approximate clustering without the approxmiation LINK: url:~/Modules/Literature/Balcan2009.pdf

Assume that is some correct “target” clustering.

Define the input has having the (c,e) property if any c-approximation to the objective function O is e-close to the target clustering.

Assume the input has the (c,e) property then it is possbile to find a clustering that is O(e)-close to the target clustering even when finding a c-approximation is NP-hard under this assumption.

For k-median and k-means, proposed algorithms for any c > 1, and for min-sum for any c > 2 when the target clusters are large.