Better Guarantees for Sparsest Cut Clustering
Abstract
We study approximation algorithms for clustering under the sparsest cut objective from the perspective of finding clusterings with low error relative to an unknown target. Under a natural property that any $c$-approximation to sparsest cut is close to the target, we give algorithms producing low-error clusterings, improving upon prior guarantees for this objective and complementing analogous results for $ k$-median and $ k$-means.
Cite
Text
Balcan. "Better Guarantees for Sparsest Cut Clustering." Annual Conference on Computational Learning Theory, 2009.Markdown
[Balcan. "Better Guarantees for Sparsest Cut Clustering." Annual Conference on Computational Learning Theory, 2009.](https://mlanthology.org/colt/2009/balcan2009colt-better/)BibTeX
@inproceedings{balcan2009colt-better,
title = {{Better Guarantees for Sparsest Cut Clustering}},
author = {Balcan, Maria-Florina},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2009},
url = {https://mlanthology.org/colt/2009/balcan2009colt-better/}
}