2026-07-25T13:34:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21013 2024-09-16T06:02:38Z ddc:004 open_access

Online k-Median with Consistent Clusters Moseley, Benjamin Newman, Heather Pruhs, Kirk k-median online algorithms learning-augmented algorithms beyond worst-case analysis We consider the problem in which n points arrive online over time, and upon arrival must be irrevocably assigned to one of k clusters where the objective is the standard k-median objective. Lower-bound instances show that for this problem no online algorithm can achieve a competitive ratio bounded by any function of n. Thus we turn to a beyond worst-case analysis approach, namely we assume that the online algorithm is a priori provided with a predicted budget B that is an upper bound to the optimal objective value (e.g., obtained from past instances). Our main result is an online algorithm whose competitive ratio (measured against B) is solely a function of k. We also give a lower bound showing that the competitive ratio of every algorithm must depend on k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Moseley and Heather Newman and Kirk Pruhs 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.20 urn:nbn:de:0030-drops-210133 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.20 eng https://creativecommons.org/licenses/by/4.0/legalcode