Online algorithms balance delay and network costs in service systems
Online Network Design with Additive Delays and Poisson Arrivals
Data Structures and Algorithms
Summary
The paper looks at how to serve people who request help from different places in a network, like cities connected by roads. The challenge is to decide where to open service points or send help so that both travel costs and waiting times are kept low. The authors use math models assuming requests arrive randomly but with known average rates. They develop fixed strategies that work nearly as well as ideal ones that know every request beforehand. Their approach works well for different kinds of network setups and is fully proven with clear performance guarantees.
What this means in practice
- •For logistics planners: Plan fixed routing and facility placement strategies for service requests that arrive unpredictably but with known average rates to keep costs and delays low.
- •For network operations teams: Use stable configurations for connecting distributed requests in computer and communication networks with random but statistically known demand patterns.
Authors
Tianhang Lu, Runtian Ren, Shengcai Liu
Abstract
We study online service systems in which requests arrive at locations in a network. A service may open a facility and connect customers, buy a subtree linking them to a root, or send a mobile server to visit them. Combining requests can save opening, network, or travel costs, but each request pays its own waiting time. The objective is the sum of these spatial costs and individual delays. We assume independent Poisson arrivals of known rates. The algorithms know how often requests occur, but observe them only upon arrival. We show that these rates suffice to make fixed spatial choices that compete with an offline optimum free to adapt to the realized input. We obtain long-run ratios of expectations below $27.249$ for facility location in finite metrics, $94.415$ for multi-root aggregation on trees, and $24.326$ for online service on trees. All three algorithms are deterministic; the multi-root algorithm also has polynomial-time preprocessing on rational inputs. The proofs connect rate-based spatial choices with lower bounds on unavoidable purchase, movement, and waiting costs. All main proofs are self-contained, and every guarantee includes the full cost of completing finite inputs.