4 papers
Online Correlation Clustering with Metric Weights
Sami Davies, Benjamin Moseley, Heather Newman
The standard online version of correlation clustering is prohibitively hard, as even randomized algorithms cannot achieve competitive ratio better than . Prior works bypass t…
Correlation Clustering with Random Partial Information
Rajath Rao K. N., Jens Schlöter, Sami Davies +2
Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, ye…
Predictive Flows for Faster Ford-Fulkerson
Sami Davies, Benjamin Moseley, Sergei Vassilvitskii +1
Recent work has shown that leveraging learned predictions can improve the running time of algorithms for bipartite matching and similar combinatorial problems. In this work, we bui…
Fast Combinatorial Algorithms for Min Max Correlation Clustering
Sami Davies, Benjamin Moseley, Heather Newman
We introduce fast algorithms for correlation clustering with respect to the Min Max objective that provide constant factor approximations on complete graphs. Our algorithms are the…