2026-07-25T13:18:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23439 2025-10-02T12:55:10Z ddc:004 open_access

Deterministic k-Median Clustering in Near-Optimal Time Costa, Martín Farokhnejad, Ermiya k-clustering k-median deterministic algorithms approximation algorithms The metric k-median problem is a textbook clustering problem. As input, we are given a metric space V of size n and an integer k, and our task is to find a subset S ⊆ V of at most k "centers" that minimizes the total distance from each point in V to its nearest center in S. Mettu and Plaxton [UAI'02] gave a randomized algorithm for k-median that computes a O(1)-approximation in Õ(nk) time. They also showed that any algorithm for this problem with a bounded approximation ratio must have a running time of Ω(nk). Thus, the running time of their algorithm is optimal up to polylogarithmic factors. For deterministic k-median, Guha et al. [FOCS'00] gave an algorithm that computes a poly(log (n/k))-approximation in Õ(nk) time, where the degree of the polynomial in the approximation is unspecified. To the best of our knowledge, this remains the state-of-the-art approximation of any deterministic k-median algorithm with this running time. This leads us to the following natural question: What is the best approximation of a deterministic k-median algorithm with near-optimal running time? We make progress in answering this question by giving a deterministic algorithm that computes a O(log(n/k))-approximation in Õ(nk) time. We also provide a lower bound showing that any deterministic algorithm with this running time must have an approximation ratio of Ω(log n/(log k + log log n)), establishing a gap between the randomized and deterministic settings for k-median. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martín Costa and Ermiya Farokhnejad 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.62 urn:nbn:de:0030-drops-234395 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.62 eng https://creativecommons.org/licenses/by/4.0/legalcode