23 citations · 146 across the 41 of their papers we have counts for
4 papers · 1 filter
Higher-Order Cheeger Inequality for Partitioning with Buffers
Konstantin Makarychev, Yury Makarychev, Liren Shan +1
We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph . The buffered expansion of a set with…
Approximation Algorithms for Norm Multiway Cut
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev +2
We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph into parts so as to separate given terminals. Recently, Chandrasekaran…
Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
Sayak Chakrabarty, Konstantin Makarychev
We show that a simple single-pass semi-streaming variant of the Pivot algorithm for Correlation Clustering gives a (3 + ε)-approximation using O(n/ε) words of memory. This is a sli…
Random Cuts are Optimal for Explainable k-Medians
Konstantin Makarychev, Liren Shan
We show that the RandomCoordinateCut algorithm gives the optimal competitive ratio for explainable k-medians in l1. The problem of explainable k-medians was introduced by Dasgupta,…