pipette
ENEnglish

A Robustified Greedy Algorithm for Online Transportation with Improved Competitive Guarantees

Ritesh Seth, Syamantak Das, Sharath Raghvendra

Preprint

En palabras de los autores

We study the online transportation problem, in which requests arriving sequentially in a metric space must be irrevocably assigned to capacitated facilities. Beyond classical logistics applications, this problem models resource-allocation tasks arising in machine learning, including online facility assignments, recommender systems, and mixture-of-experts routing. We introduce Robustified Greedy (RG), a deterministic generalization of the Robust Matching algorithm that achieves a competitive ratio of , improving upon the state-of-the-art bounds of (Arndt et al., SOSA 2026) and (Harada and Itoh, ICALP 2025). RG also retains the metric-sensitive guarantee established for Robust Matching (RM) (Nayyar and Raghvendra, FOCS 2017), achieving a competitive ratio of in -dimensional Euclidean spaces for fixed . No comparable metric-sensitive guarantee is known for the transportation algorithms of Arndt et al.\ or Harada and Itoh. Beyond these competitive guarantees, RG provides a simple explanation for its decisions. It favors the natural nearest-neighbor assignment and, for suitable parameters, departs from this choice only when it identifies a reassignment that reduces the cost of its maintained auxiliary matching, thereby correcting accumulated assignment costs. We also prove that nearest-neighbor assignments account for a guaranteed fraction of RG's total cost, approaching one-half for appropriate parameters, even under adversarial arrivals. Experiments on real-world datasets corroborate the theory: RG achieves lower cost-to-\textsc{Opt} ratios than the competing algorithms while retaining a substantial nearest-neighbor component in its cost.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.