2 papers
cs.DS2026
Improved Algorithms and Lower Bounds for Parametrized Metrical Service Systems
Junhao Gan, Xiao Sun, Seeun William Umboh
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…
cs.DS2026
Online Matching with Size-Based and Convex Delays
Junhao Gan, Xiao Sun, Seeun William Umboh
We study the online min-cost perfect matching with delay (MPMD) problem where requests arrive in a metric space of points. In MPMD, an algorithm can choose to match a reque…