April 26, 2024, 4:42 a.m. | Vicente Balmaseda, Ying Xu, Yixin Cao, Nate Veldt

cs.LG updates on arXiv.org arxiv.org

arXiv:2404.16131v1 Announce Type: cross
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 …

abstract algorithms analysis applications approximation arxiv biology cluster clustering computational computational biology cs.ds cs.lg cs.si faster graph improving minimum network np-hard social type

Data Engineer

@ Lemon.io | Remote: Europe, LATAM, Canada, UK, Asia, Oceania

Artificial Intelligence – Bioinformatic Expert

@ University of Texas Medical Branch | Galveston, TX

Lead Developer (AI)

@ Cere Network | San Francisco, US

Research Engineer

@ Allora Labs | Remote

Ecosystem Manager

@ Allora Labs | Remote

Founding AI Engineer, Agents

@ Occam AI | New York