# On Complexity of 1-Center in Various Metrics

arXiv: https://arxiv.org/abs/2112.03222 · HTML: https://mlsanity.com/paper/2112.03222/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 6 Dec 2021.

## Builds on (most cited first, 11 of 11)

- [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016)
- [Hardness of Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1803.00904/) (2018)
- [Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)](https://mlsanity.com/paper/1412.0348/) (2014)
- [On Approximability of Clustering Problems Without Candidate Centers](https://mlsanity.com/paper/2010.00087/) (2020)
- [On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product](https://mlsanity.com/paper/1802.02325/) (2018)
- [Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping](https://mlsanity.com/paper/1502.01063/) (2015)
- [On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry](https://mlsanity.com/paper/1709.05282/) (2017)
- [On the Complexity of Closest Pair via Polar-Pair of Point-Sets](https://mlsanity.com/paper/1608.03245/) (2016)
- [Polyline Simplification has Cubic Complexity](https://mlsanity.com/paper/1810.00621/) (2018)
- [Scheduling Lower Bounds via AND Subset Sum](https://mlsanity.com/paper/2003.07113/) (2020)
- [Approximating the Median under the Ulam Metric](https://mlsanity.com/paper/2011.00868/) (2020)

## Built on by (most cited first, 1 of 1)

- [Can You Solve Closest String Faster than Exhaustive Search?](https://mlsanity.com/paper/2305.16878/) (2023)

## Abstract (arXiv)

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. bullet Small d: 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. bullet Large d: When d=Omega(n), we extend our conditional lower bound to rule out subquartic 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 tildeOvarepsilon(nd+n2√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.