Conference PaperOnline k-Median with Consistent ClustersMoseley, Benjamin; Newman, Heather; Pruhs, KirkKumar, Amit; Ron-Zewi, NogaWe 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 Informatik2024-01-0110563544317317-3171868-8969978-3-95977-348-5https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.202121744; 1845146k-medianonline algorithmslearning-augmented algorithmsbeyond worst-case analysisTheory of computation → Online algorithms22 pages1055498 bytesapplication/pdfCreative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccessNational Science Foundation