Competitive Analysis of Online Facility Assignment Algorithms on Discrete Grid Graphs: Performance Bounds and Remediation Strategies
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911424955023360 |
|---|---|
| author | Alif, Lamya Saoda, Raian Tasnim Afrin, Sumaiya Riad, Md. Rawha Siddiqi Rahat, Md. Tanzeem Hasan, Md Manzurul |
| author_facet | Alif, Lamya Saoda, Raian Tasnim Afrin, Sumaiya Riad, Md. Rawha Siddiqi Rahat, Md. Tanzeem Hasan, Md Manzurul |
| contents | We study the \emph{Online Facility Assignment} (OFA) problem on a discrete $r\times c$ grid graph under the standard model of Ahmed, Rahman, and Kobourov: a fixed set of facilities is given, each with limited capacity, and an online sequence of unit-demand requests must be irrevocably assigned upon arrival to an available facility, incurring Manhattan ($L_1$) distance cost. We investigate how the discrete geometry of grids interacts with capacity depletion by analyzing two natural baselines and one capacity-aware heuristic. First, we give explicit adversarial sequences on grid instances showing that purely local rules can be forced into large competitive ratios: (i) a capacity-sensitive weighted-Voronoi heuristic (\textsc{CS-Voronoi}) can suffer cascading \emph{region-collapse} effects when nearby capacity is exhausted; and (ii) nearest-available \textsc{Greedy} (with randomized tie-breaking) can be driven into repeated long reassignments via an \emph{oscillation} construction. These results formalize geometric failure modes that are specific to discrete $L_1$ metrics with hard capacities. Motivated by these lower bounds, we then discuss a semi-online extension in which the algorithm may delay assignment for up to $τ$ time steps and solve each batch optimally via a min-cost flow computation. We present this batching framework as a remediation strategy and delineate the parameters that govern its performance, while leaving sharp competitive guarantees for this semi-online variant as an open direction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_05953 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Competitive Analysis of Online Facility Assignment Algorithms on Discrete Grid Graphs: Performance Bounds and Remediation Strategies Alif, Lamya Saoda, Raian Tasnim Afrin, Sumaiya Riad, Md. Rawha Siddiqi Rahat, Md. Tanzeem Hasan, Md Manzurul Data Structures and Algorithms We study the \emph{Online Facility Assignment} (OFA) problem on a discrete $r\times c$ grid graph under the standard model of Ahmed, Rahman, and Kobourov: a fixed set of facilities is given, each with limited capacity, and an online sequence of unit-demand requests must be irrevocably assigned upon arrival to an available facility, incurring Manhattan ($L_1$) distance cost. We investigate how the discrete geometry of grids interacts with capacity depletion by analyzing two natural baselines and one capacity-aware heuristic. First, we give explicit adversarial sequences on grid instances showing that purely local rules can be forced into large competitive ratios: (i) a capacity-sensitive weighted-Voronoi heuristic (\textsc{CS-Voronoi}) can suffer cascading \emph{region-collapse} effects when nearby capacity is exhausted; and (ii) nearest-available \textsc{Greedy} (with randomized tie-breaking) can be driven into repeated long reassignments via an \emph{oscillation} construction. These results formalize geometric failure modes that are specific to discrete $L_1$ metrics with hard capacities. Motivated by these lower bounds, we then discuss a semi-online extension in which the algorithm may delay assignment for up to $τ$ time steps and solve each batch optimally via a min-cost flow computation. We present this batching framework as a remediation strategy and delineate the parameters that govern its performance, while leaving sharp competitive guarantees for this semi-online variant as an open direction. |
| title | Competitive Analysis of Online Facility Assignment Algorithms on Discrete Grid Graphs: Performance Bounds and Remediation Strategies |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.05953 |