{"ID":2883912,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.08381","arxiv_id":"2508.08381","title":"Competitive Online Transportation Simplified","abstract":"The setting for the online transportation problem is a metric space $M$, populated by $m$ parking garages of varying capacities. Over time cars arrive in $M$, and must be irrevocably assigned to a parking garage upon arrival in a way that respects the garage capacities. The objective is to minimize the aggregate distance traveled by the cars. In 1998, Kalyanasundaram and Pruhs conjectured that there is a $(2m-1)$-competitive deterministic algorithm for the online transportation problem, matching the optimal competitive ratio for the simpler online metric matching problem. Recently, Harada and Itoh presented the first $O(m)$-competitive deterministic algorithm for the online transportation problem. Our contribution is an alternative algorithm design and analysis that we believe is simpler.","short_abstract":"The setting for the online transportation problem is a metric space $M$, populated by $m$ parking garages of varying capacities. Over time cars arrive in $M$, and must be irrevocably assigned to a parking garage upon arrival in a way that respects the garage capacities. The objective is to minimize the aggregate distan...","url_abs":"https://arxiv.org/abs/2508.08381","url_pdf":"https://arxiv.org/pdf/2508.08381v2","authors":"[\"Stephen Arndt\",\"Benjamin Moseley\",\"Kirk Pruhs\",\"Marc Uetz\"]","published":"2025-08-11T18:08:07Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}