Subgraph Counting: Color Coding beyond Trees
Venkatesan T. Chakaravarthy, Michael Kapralov, et al.
IPDPS 2016
The k-supplier problem is a fundamental location problem that involves opening k facilities to minimize the maximum distance of any client to an open facility. We consider the k-supplier problem in Euclidean metrics (of arbitrary dimension) and present an algorithm with approximation ratio 1 + √3 < 2.74. This improves upon the previously known 3-approximation algorithm, which also holds for general metrics. Our result is almost best possible as the Euclidean k-supplier problem is NP-hard to approximate better than a factor of √7 > 2.64. We also present a nearly linear time algorithm for the Euclidean k-supplier in constant dimensions that achieves an approximation ratio better than three.
Venkatesan T. Chakaravarthy, Michael Kapralov, et al.
IPDPS 2016
Nikhil Bansal, Danny Z. Chen, et al.
Algorithmica (New York)
Dmitriy Katz-Rogozhnikov, Baruch Schieber, et al.
SPAA 2016
Viswanath Nagarajan, Kanthi Sarpatwar, et al.
APPROX/RANDOM 2015