Showing 2026Show all
3 papers · 1 filter
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…
cs.DS2026
A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
Philip Cervenjak, Junhao Gan, Naonori Kakimura +2
Connected Submodular Maximization (CSM) is a graph problem with important applications to wireless network deployment, path planning, epidemic outbreaks, and cancer genome studies.…