Problem
In online facility assignment on an r by c grid, requests arrive one at a time and must be assigned immediately to capacity-limited facilities while incurring Manhattan distance cost.
Back to research
arXiv ยท February 2026
Competitive Analysis of Online Facility Assignment Algorithms on Discrete Grid Graphs
A study of grid-based online assignment, capacity depletion, and remediation strategies by Lamya Alif, Raian Tasnim Saoda, Sumaiya Afrin, Md. Rawha Siddiqi Riad, Md. Tanzeem Rahat, and Md Manzurul Hasan.
Why It Matters
Online assignment decisions appear in logistics, service systems, resource allocation, and routing. Grid geometry makes local decisions attractive, but capacity limits can make them fragile.
Core Idea
The paper studies how local rules fail under adversarial sequences, then considers semi-online batching with min-cost flow as a remediation strategy.
Main Result
The work identifies capacity-sensitive weighted-Voronoi and nearest-available greedy failure modes, including region collapse and oscillation constructions on discrete grids.
What Was Difficult
The challenge is exposing failures that are specific to hard capacity constraints and discrete L1 geometry, rather than only measuring average-case behavior.
Resources
Open Directions
- Can semi-online batching yield sharp competitive bounds?
- Which grid geometries make local assignment rules most brittle?
- How should practical systems choose the delay parameter for batching?