| Autor: |
Baligacs, Julia, Disser, Yann, Mosis, Nils, Weckbecker, David |
| Rok vydání: |
2022 |
| Předmět: |
|
| Zdroj: |
LNCS volume 13538 (2022) 154-171 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1007/978-3-031-18367-6_8 |
| Popis: |
We consider the open online dial-a-ride problem, where transportation requests appear online in a metric space and need to be served by a single server. The objective is to minimize the completion time until all requests have been served. We present a new, parameterized algorithm for this problem and prove that it attains a competitive ratio of $1 + \varphi \approx 2.618$ for some choice of its parameter, where $\varphi$ is the golden ratio. This improves the best known bounds for open online dial-a-ride both for general metric spaces as well as for the real line. We also give a lower bound of~$2.457$ for the competitive ratio of our algorithm for any parameter choice. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
