2026-07-24T12:23:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18826 2024-03-06T11:02:40Z ddc:004 open_access

On Complexity of 1-Center in Various Metrics Abboud, Amir Bateni, MohammadHossein Cohen-Addad, Vincent Karthik C. S. Seddighin, Saeed Center Clustering Edit metric Ulam metric Hamming metric Fine-grained Complexity Approximation 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. Assuming the hitting set conjecture (HSC), we show that when d = ω(log n), no subquadratic algorithm can solve the 1-center problem in any of the 𝓁_p-metrics, or in the edit or Ulam metrics. - Large d. When d = Ω(n), we extend our conditional lower bound to rule out subquartic algorithms for the 1-center problem in edit metric (assuming Quantified SETH). On the other hand, we give a (1+ε)-approximation for 1-center in the Ulam metric with running time O_{ε}̃(nd+n²√d). We also strengthen some of the above lower bounds by allowing approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amir Abboud and MohammadHossein Bateni and Vincent Cohen-Addad and Karthik C. S. and Saeed Seddighin 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.1 urn:nbn:de:0030-drops-188260 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.1 eng https://creativecommons.org/licenses/by/4.0/legalcode