{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicrvpsgr5bjoezaemwnifigikbpleo5fzu4t6fbu3lddjak2a27py",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3me5xdpx32xd2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.05953v1",
  "publishedAt": "2026-02-06T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Lamya Alif",
    "Raian Tasnim Saoda",
    "Sumaiya Afrin",
    "Md. Rawha Siddiqi Riad",
    "Md. Tanzeem Rahat",
    "Md Manzurul Hasan"
  ],
  "textContent": "**Authors:** Lamya Alif, Raian Tasnim Saoda, Sumaiya Afrin, Md. Rawha Siddiqi Riad, Md. Tanzeem Rahat, Md Manzurul Hasan\n\nWe 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"
}