From the 1 of 9 linked papers with an AI index.
9 papers
Online TCP Acknowledgment under General Delays
Sujoy Bhore, MichaÅ PawÅowski, Seeun William Umboh
The paper investigates the online TCP acknowledgment problem under generalized delay-cost models, analyzing the competitive performance of greedy algorithms for batch-aware and bat…
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.…
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…
Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
Michael Dinitz, Jeremy T. Fineman, Seeun William Umboh
This paper considers using predictions in the context of the online Joint Replenishment Problem with Deadlines (JRP-D). Prior work includes asymptotically optimal competitive ratio…