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.
| Original language | English |
|---|---|
| Publisher | ArXiv.org |
| Number of pages | 12 |
| Publication status | Published - 11 Aug 2025 |
Keywords
- cs.DS
Fingerprint
Dive into the research topics of 'Competitive Online Transportation Simplified'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver