4 papers · 1 filter
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…
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…
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…
Online Facility Assignments on Polygons
Sumaiya Malik, Reyan Ahmed, Md. Manzurul Hasan
We study the online facility assignment problem on regular polygons, where all sides are of equal length. The influence of specific geometric settings has remained mostly unexplore…