14 citations · 51 across the 29 of their papers we have counts for
4 papers · 1 filter
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto +4
Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and t…
The Karger-Stein Algorithm is Optimal for -cut
Anupam Gupta, Euiwoong Lee, Jason Li
In the -cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into connected components. Algorithms…
The Number of Minimum -Cuts: Improving the Karger-Stein Bound
Anupam Gupta, Euiwoong Lee, Jason Li
Given an edge-weighted graph, how many minimum -cuts can it have? This is a fundamental question in the intersection of algorithms, extremal combinatorics, and graph theory. It…
Tight FPT Approximations for -Median and -Means
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar +2
We investigate the fine-grained complexity of approximating the classical -median / -means clustering problems in general metric spaces. We show how to improve the approximat…