23 citations · 146 across the 41 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016★ 1 cited
Metric Perturbation Resilience
Konstantin Makarychev, Yury Makarychev
We study the notion of perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A clustering problem is -perturbation resilient if the…
cs.DS2016
Robust algorithms with polynomial loss for near-unanimity CSPs
Víctor Dalmau, Marcin Kozik, Andrei Krokhin +3
An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain…
math.MG2016★ 8 cited
A Union of Euclidean Metric Spaces is Euclidean
Konstantin Makarychev, Yury Makarychev
Suppose that a metric space is the union of two metric subspaces and that embed into Euclidean space with distortions and , respectively. We prove that then…