Competitive Online Transportation Simplified
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918163550044160 |
|---|---|
| author | Arndt, Stephen Moseley, Benjamin Pruhs, Kirk Uetz, Marc |
| author_facet | Arndt, Stephen Moseley, Benjamin Pruhs, Kirk Uetz, Marc |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08381 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Competitive Online Transportation Simplified Arndt, Stephen Moseley, Benjamin Pruhs, Kirk Uetz, Marc Data Structures and Algorithms 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. |
| title | Competitive Online Transportation Simplified |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.08381 |