Problem
Facilities occupy the vertices of a regular polygon, customers arrive on polygon edges, and greedy assignment sends each arrival to the nearest currently free facility.
Back to research
arXiv preprint 2512.00506
Expected Cost of Greedy Online Facility Assignment on Regular Polygons
A Scholar-listed online algorithms paper by Md. Rawha Siddiqi Riad, Md. Tanzeem Rahat, and Md. Manzurul Hasan on expected assignment cost in regular polygon metrics.
Why It Matters
The model gives a clean stochastic setting for studying how local online assignment decisions accumulate cost under capacity constraints and geometric symmetry.
Core Idea
The work characterizes expected remaining cost with a finite-horizon recurrence, then uses dihedral symmetry to reduce the number of states in the dynamic program.
Main Result
The analysis combines exact recurrence, symmetry reduction, deterministic numerical integration for small polygons, and Monte Carlo simulation for larger instances.
What Was Difficult
The key challenge is keeping the continuous arrival process, tie-breaking behavior, and future occupancy states in one computable value function.
Resources
Open Directions
- Can the recurrence scale to larger polygons without relying mainly on simulation?
- What changes under nonuniform or correlated arrivals?
- Can expected-cost analysis be connected to worst-case competitive guarantees?