






















We study a greedy online facility assignment process on a regular $n$-gon, where unit-capacity facilities occupy the vertices and customers arrive sequentially at uniformly random locations on polygon edges. Each arrival is irrevocably assigned to the nearest currently free facility under the shortest edge-walk metric, with uniform tie-breaking among equidistant choices. Our main theoretical result is an exact value-function characterization: for every occupancy state $S\subseteq V$, the expected remaining cost $V(S)$ satisfies a finite-horizon integral recurrence obtained by conditioning on the random arrival edge and position. To make this recurrence computationally effective, we exploit dihedral symmetry of the regular polygon and show that $V(S)$ is invariant under rotations and reflections, enabling canonicalization and symmetry-reduced dynamic programming. For small $n$, we evaluate the recurrence accurately using deterministic numerical integration over piecewise-linear distance regions,; for larger $n$, we estimate the expected total cost via direct Monte Carlo simulation of the online process and report $95\%$ confidence intervals. Our computations validate the recurrence (including a closed-form check for the square, $n=4$) and indicate that the total expected cost increases with $n$, while the per-customer expected travel distance grows gradually as remaining free vertices become farther on average. \keywords{Online algorithms \and Facility assignment \and Expected cost \and Regular polygons \and Symmetry reduction \and Monte Carlo}
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。