5 papers
Estimating Random-Walk Probabilities in Directed Graphs
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup +2
We study discounted random walks in directed graphs. In each step, the walk either terminates with a constant probability , or proceeds to a random out-neighbor. Our goal is to…
Static to Dynamic Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee +7
Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to clu…
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…
Solving the Correlation Cluster LP in Sublinear Time
Nairen Cao, Vincent Cohen-Addad, Shi Li +7
Correlation Clustering is a fundamental and widely-studied problem in unsupervised learning and data mining. The input is a graph and the goal is to construct a clustering minimizi…
Bounding a Polygon by a Minimum Number of Vertices
Mikkel Abrahamsen, Jack Stade, Shuyi Yan +1
Suppose that a polygon is given as an array containing the vertices in counterclockwise order. We analyze how many vertices (including the index of each of these vertices) we n…