A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909589218263040 |
|---|---|
| author | Harada, Tsubasa Itoh, Toshiya |
| author_facet | Harada, Tsubasa Itoh, Toshiya |
| contents | For the online transportation problem with $m$ server sites, it has long been known that the competitive ratio of any deterministic algorithm is at least $2m-1$. Kalyanasundaram and Pruhs conjectured in 1998 that a deterministic $(2m-1)$-competitive algorithm exists for this problem, a conjecture that has remained open for over two decades.
In this paper, we propose a new deterministic algorithm named Subtree-Decomposition for the online transportation problem and show that it achieves a competitive ratio of at most $8m-5$. This is the first $O(m)$-competitive deterministic algorithm, coming close to the lower bound of $2m-1$ within a constant factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03778 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Nearly Optimal Deterministic Algorithm for Online Transportation Problem Harada, Tsubasa Itoh, Toshiya Data Structures and Algorithms Discrete Mathematics For the online transportation problem with $m$ server sites, it has long been known that the competitive ratio of any deterministic algorithm is at least $2m-1$. Kalyanasundaram and Pruhs conjectured in 1998 that a deterministic $(2m-1)$-competitive algorithm exists for this problem, a conjecture that has remained open for over two decades. In this paper, we propose a new deterministic algorithm named Subtree-Decomposition for the online transportation problem and show that it achieves a competitive ratio of at most $8m-5$. This is the first $O(m)$-competitive deterministic algorithm, coming close to the lower bound of $2m-1$ within a constant factor. |
| title | A Nearly Optimal Deterministic Algorithm for Online Transportation Problem |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2406.03778 |