1 citations · 2 across the 20 of their papers we have counts for
5 papers · 1 filter
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…
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…
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.…
Online TCP Acknowledgment under General Delays
Sujoy Bhore, Michał Pawłowski, Seeun William Umboh
In a seminal work, Dooly, Goldman, and Scott (STOC 1998; JACM 2001) introduced the classic Online TCP Acknowledgment} problem: a sequence of packets arrives over time, and the…
Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
David Shmoys, Varun Suriyanarayana, Seeun William Umboh
The Joint Replenishment Problem (JRP) is a classical inventory management problem, that aims to model the trade-off between coordinating orders for multiple commodities (and their…