3 papers
cs.DS2026
Exact and Asymptotic Analysis of Greedy Online Facility Assignment on Cycle Metrics
Md. Tanzeem Rahat, Md. Rawha Siddiqi Riad, Md. Manzurul Hasan
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 c…
cs.DS2026
Competitive Analysis of Online Facility Assignment Algorithms on Discrete Grid Graphs: Performance Bounds and Remediation Strategies
Lamya Alif, Raian Tasnim Saoda, Sumaiya Afrin +3
We study the \emph{Online Facility Assignment} (OFA) problem on a discrete grid graph under the standard model of Ahmed, Rahman, and Kobourov: a fixed set of facilities…
cs.DS2026
Expected Cost of Greedy Online Facility Assignment on Regular Polygons (v3)
Md. Rawha Siddiqi Riad, Md. Tanzeem Rahat, Md. Manzurul Hasan
We study a greedy online facility assignment process on a regular -gon, where unit-capacity facilities occupy the vertices and customers arrive sequentially at uniformly random…