Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
<|reference_start|>Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better: 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.<|reference_end|>
@article{balmaseda2024combinatorial,
    title={Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and
  Better},
    author={Vicente Balmaseda, Ying Xu, Yixin Cao, Nate Veldt},
    journal={arXiv preprint arXiv:2404.16131},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.16131},
    primaryClass={cs.DS cs.LG cs.SI}
}