On Complexity of 1-Center in Various Metrics

12/06/2021
by   Amir Abboud, et al.
0

We consider the classic 1-center problem: Given a set P of n points in a metric space find the point in P that minimizes the maximum distance to the other points of P. We study the complexity of this problem in d-dimensional ℓ_p-metrics and in edit and Ulam metrics over strings of length d. Our results for the 1-center problem may be classified based on d as follows. ∙ Small d: We provide the first linear-time algorithm for 1-center problem in fixed-dimensional ℓ_1 metrics. On the other hand, assuming the hitting set conjecture (HSC), we show that when d=ω(log n), no subquadratic algorithm can solve 1-center problem in any of the ℓ_p-metrics, or in edit or Ulam metrics. ∙ Large d. When d=Ω(n), we extend our conditional lower bound to rule out sub quartic algorithms for 1-center problem in edit metric (assuming Quantified SETH). On the other hand, we give a (1+ϵ)-approximation for 1-center in Ulam metric with running time Õ_̃ϵ̃(nd+n^2√(d)). We also strengthen some of the above lower bounds by allowing approximations or by reducing the dimension d, but only against a weaker class of algorithms which list all requisite solutions. Moreover, we extend one of our hardness results to rule out subquartic algorithms for the well-studied 1-median problem in the edit metric, where given a set of n strings each of length n, the goal is to find a string in the set that minimizes the sum of the edit distances to the rest of the strings in the set.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset