Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
Abstract
Cluster deletion is an NP-hard graph clustering objective with applications in computational biology and social network analysis, where the goal is to delete a minimum number of edges to partition a graph into cliques. We first provide a tighter analysis of two previous approximation algorithms, improving their approximation guarantees from 4 to 3. Moreover, we show that both algorithms can be derandomized in a surprisingly simple way, by greedily taking a vertex of maximum degree in an auxiliary graph and forming a cluster around it. One of these algorithms relies on solving a linear program. Our final contribution is to design a new and purely combinatorial approach for doing so that is far more scalable in theory and practice.
Cite
Text
Balmaseda et al. "Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better." International Conference on Machine Learning, 2024.Markdown
[Balmaseda et al. "Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/balmaseda2024icml-combinatorial/)BibTeX
@inproceedings{balmaseda2024icml-combinatorial,
title = {{Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better}},
author = {Balmaseda, Vicente and Xu, Ying and Cao, Yixin and Veldt, Nate},
booktitle = {International Conference on Machine Learning},
year = {2024},
pages = {2586-2606},
volume = {235},
url = {https://mlanthology.org/icml/2024/balmaseda2024icml-combinatorial/}
}