3 citations · 5 across the 7 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.DS2016
Algorithmic and Hardness Results for the Hub Labeling Problem
Haris Angelidakis, Yury Makarychev, Vsevolod Oparin
There has been significant success in designing highly efficient algorithms for distance and shortest-path queries in recent years; many of the state-of-the-art algorithms use the…
cs.DS2016★ 2 cited
An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut
Haris Angelidakis, Yury Makarychev, Pasin Manurangsi
We construct an improved integrality gap instance for the Calinescu-Karloff-Rabani LP relaxation of the Multiway Cut problem. In particular, for terminals, our inst…