arXiv preprint ·
Exact and Asymptotic Analysis of Greedy Online Facility Assignment on Cycle Metrics
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We identify the free-facility gaps of greedy online assignment on a cycle with the discrete additive coalescent and use this connection to determine the exact expected assignment cost. The cycle has circumference $n$, with one unit-capacity facility at each integer point and $n$ independent uniform arrivals. Each request is assigned immediately to a nearest free facility. The conditional one-step cost is the sum of squared gap lengths divided by $4n$. A uniform cyclic-order argument identifies the unordered gap process with additive coalescence. The classical Cayley-tree representation then reduces the accumulated cost to a two-vertex distance functional, yielding \[ G_n=\frac n4\sum_{d=0}^{n-1}\prod_{j=1}^{d}\left(1-\frac jn\right) \sim\frac14\sqrt{\frac\pi2}\,n^{3/2}. \] The formula requires a linear number of scalar recurrence steps to evaluate. We also obtain an asymptotic upper bound of $π\sqrt3/2$ on the ratio of expected greedy cost to expected offline optimum under this arrival model. An exact rational Bellman calculation shows that greedy is optimal for three facilities but exceeds the optimal online expected cost by $1/512$ for four facilities. Independent exact recurrences and finite tree enumeration provide reproducible checks of the analysis.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Cascade: GPU-Accelerated Out-of-Core Suffix Array Construction for LLM Corpora
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Optimal High Probability Bounds for Random Order Online Sorting
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.