17 citations · 25 across the 3 of their papers we have counts for
4 papers
Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems
David García-Soriano, Atsushi Miyauchi
The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most clusters using independ…
Approximate Dual Separation for the Cluster LP: a 1.387-approximation for Correlation Clustering
David García-Soriano, Antoine Schohn
We give a -approximation for correlation clustering on complete graphs, improving the previous best factor of of Cao et al. (STOC'24). Our first main contribu…
Finding Densest -Connected Subgraphs
Francesco Bonchi, David García-Soriano, Atsushi Miyauchi +1
Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph dis…
Query-Efficient Correlation Clustering
David García-Soriano, Konstantin Kutzkov, Francesco Bonchi +1
Correlation clustering is arguably the most natural formulation of clustering. Given n objects and a pairwise similarity measure, the goal is to cluster the objects so that, to the…