5 citations · 6 across the 2 of their papers we have counts for
2 papers
cs.DS2014★ 1 cited
Constant Factor Approximation for Balanced Cut in the PIE model
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation-invariant random edges (PIE). Our model is much more general than p…
cs.DS2014★ 5 cited
Correlation Clustering with Noisy Partial Information
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clusterin…