DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.11

Improved Algorithms and Lower Bounds for Parametrized Metrical Service Systems

Authors: Junhao Gan, Xiao Sun, and Seeun William Umboh

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

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 ≥ 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 ≥ 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 ≥ 3.

Cite as

Junhao Gan, Xiao Sun, and Seeun William Umboh. Improved Algorithms and Lower Bounds for Parametrized Metrical Service Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gan_et_al:LIPIcs.APPROX/RANDOM.2026.11,
  author =	{Gan, Junhao and Sun, Xiao and Umboh, Seeun William},
  title =	{{Improved Algorithms and Lower Bounds for Parametrized Metrical Service Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.11},
  URN =		{urn:nbn:de:0030-drops-277289},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.11},
  annote =	{Keywords: online algorithms, competitive analysis, metrical service systems, metrical task systems}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.25

Online Matching with Size-Based and Convex Delays

Authors: Junhao Gan, Xiao Sun, and Seeun William Umboh

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

We study the online min-cost perfect matching with delay (MPMD) problem where m requests arrive in a metric space of n points. In MPMD, an algorithm can choose to match a request or to delay, and the objective is to minimise the sum of connection and delay costs. The connection cost of a match is the distance between the locations of two matched requests in the metric, and the increase of the delay cost is a function of the set of unmatched requests at every moment. In this paper, we study two different types of delay functions, size-based (MPMD-Size) and convex delays (MPMD-Convex). The study of MPMD-Size was initiated by Deryckere and Umboh (APPROX/RANDOM 2023) where the instantaneous delay increment is a non-negative monotone function of the number of unmatched requests. We give an exponential improvement on the lower bounds for the deterministic and randomized competitive ratios. We also give improved upper bounds in terms of n, as opposed to Deryckere and Umboh’s upper bounds that were functions of m, which can be much larger than n. Our results settle the deterministic competitive ratio (up to constants). At the heart of these results is a succinct encoding scheme of MPMD-Size on a given n-point metric as a metrical task system problem on a 2^{n-1}-point metric. We also consider MPMD-Convex proposed by Liu et al. (ISAAC 2018) where the delay cost incurred by each request is a uniform convex delay function of the time difference between its arrival time and the moment that it is matched by the algorithm. They focused on delay functions f that are unbounded, non-decreasing, continuous, and satisfy f(0) = f'(0) = 0, and showed that the deterministic competitive ratio is Ω(n) for n-point uniform metrics. We show that, surprisingly, when f is a non-negative, monotone polynomial with f'(0) > 0, there is an O(1)-competitive deterministic algorithm for uniform metrics. Our result completes our understanding of MPMD-Convex on uniform metrics for a broad class of functions.

Cite as

Junhao Gan, Xiao Sun, and Seeun William Umboh. Online Matching with Size-Based and Convex Delays. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gan_et_al:LIPIcs.APPROX/RANDOM.2026.25,
  author =	{Gan, Junhao and Sun, Xiao and Umboh, Seeun William},
  title =	{{Online Matching with Size-Based and Convex Delays}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{25:1--25:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.25},
  URN =		{urn:nbn:de:0030-drops-277428},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.25},
  annote =	{Keywords: online algorithms with delays, competitive analysis, matching}
}

Search Results

Documents authored by Sun, Xiao

Improved Algorithms and Lower Bounds for Parametrized Metrical Service Systems

Abstract

Cite as

Online Matching with Size-Based and Convex Delays

Abstract

Cite as

Thanks for your feedback!

Could not send message