{"ID":6138128,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T07:25:32.492443187Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07098","arxiv_id":"2607.07098","title":"Improved Algorithms and Lower Bounds for Parametrized Metrical Service Systems","abstract":"We consider the parametrized setting of the classical metrical service system (MSS) problem first studied by Bubeck and Rabani (APPROX/RANDOM 2020). In this setting, the adversary is restricted to a set of $m$ distinct request types, known to the algorithm in advance. The goal is to obtain competitive ratio bounds in terms of $m$. In this work, we make significant progress in understanding the landscape of parametrized MSS and resolve several open problems from Bubeck and Rabani. Our first main result is a tight bound for parametrized MSS on weighted stars. Previously, Bubeck and Rabani gave a randomized lower bound of $Ω(m)$ and deterministic upper bound of $O(2^m)$. We show that, surprisingly, a deterministic $O(m)$-competitive algorithm exists, matching the randomized lower bound. Our key insight is an interval covering formulation of MSS on weighted stars which enables an application of the primal-dual method. Our second main contribution is an improved lower bound construction for parametrized MSS on hierarchically separated trees (HSTs). Bubeck and Rabani's construction gave a $ω(1)$ lower bound when $m \\geq 6$. Our improved lower bounds are tight for $2$-level HSTs and also rule out $O(1)$-competitive algorithms on HSTs when the parameter $m\\geq 4$. We also complement these results by giving a deterministic $O(1)$-competitive algorithm on general metrics when $m=2$ while showing that it is impossible when $m\\geq 3$.","short_abstract":"We consider the parametrized setting of the classical metrical service system (MSS) problem first studied by Bubeck and Rabani (APPROX/RANDOM 2020). In this setting, the adversary is restricted to a set of $m$ distinct request types, known to the algorithm in advance. The goal is to obtain competitive ratio bounds in t...","url_abs":"https://arxiv.org/abs/2607.07098","url_pdf":"https://arxiv.org/pdf/2607.07098v1","authors":"[\"Junhao Gan\",\"Xiao Sun\",\"Seeun William Umboh\"]","published":"2026-07-08T07:32:26Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}