4 papers
Pivot based correlation clustering in the presence of good clusters
David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan
The classic pivot based clustering algorithm of Ailon, Charikar and Chawla [JACM'08] is factor 3, but all concrete examples showing that it is no better than 3 are based on some ve…
A Faster Algorithm for Constrained Correlation Clustering
Nick Fischer, Evangelos Kipouridis, Jonas Klausen +1
In the Correlation Clustering problem we are given nodes, and a preference for each pair of nodes indicating whether we prefer the two endpoints to be in the same cluster or no…
Hashing for Sampling-Based Estimation
Anders Aamand, Ioana O. Bercea, Jakob Bæk Tejs Houen +2
Hash-based sampling and estimation are common themes in computing. Using hashing for sampling gives us the coordination needed to compare samples from different sets. Hashing is al…
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
Shyam Narayanan, Václav RozhoÅ, Jakub TÄtek +1
Suppose we have a memory storing s and s and we want to estimate the frequency of s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a bloc…