23 citations · 146 across the 41 of their papers we have counts for
4 papers · 1 filter
Explainable k-means. Don't be greedy, plant bigger trees!
Konstantin Makarychev, Liren Shan
We provide a new bi-criteria competitive algorithm for explainable -means clustering. Explainable -means was recently introduced by Dasgupta, Frost, Mos…
Local Correlation Clustering with Asymmetric Classification Errors
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev +1
In the Correlation Clustering problem, we are given a complete weighted graph with its edges labeled as "similar" and "dissimilar" by a noisy binary classifier. For a clusterin…
Correlation Clustering with Asymmetric Classification Errors
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev +1
In the Correlation Clustering problem, we are given a weighted graph with its edges labeled as "similar" or "dissimilar" by a binary classifier. The goal is to produce a cluste…
Near-optimal Algorithms for Explainable k-Medians and k-Means
Konstantin Makarychev, Liren Shan
We consider the problem of explainable -medians and -means introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian~(ICML 2020). In this problem, our goal is to find a thres…