License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.15
URN: urn:nbn:de:0030-drops-102543
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10254/
Birx, Alexander ;
Disser, Yann
Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line
Abstract
The online Dial-a-Ride problem is a fundamental online problem in a metric space, where transportation requests appear over time and may be served in any order by a single server with unit speed. Restricted to the real line, online Dial-a-Ride captures natural problems like controlling a personal elevator. Tight results in terms of competitive ratios are known for the general setting and for online TSP on the line (where source and target of each request coincide). In contrast, online Dial-a-Ride on the line has resisted tight analysis so far, even though it is a very natural online problem.
We conduct a tight competitive analysis of the Smartstart algorithm that gave the best known results for the general, metric case. In particular, our analysis yields a new upper bound of 2.94 for open, non-preemptive online Dial-a-Ride on the line, which improves the previous bound of 3.41 [Krumke'00]. The best known lower bound remains 2.04 [SODA'17]. We also show that the known upper bound of 2 [STACS'00] regarding Smartstart's competitive ratio for closed, non-preemptive online Dial-a-Ride is tight on the line.
BibTeX - Entry
@InProceedings{birx_et_al:LIPIcs:2019:10254,
author = {Alexander Birx and Yann Disser},
title = {{Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {15:1--15:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-100-9},
ISSN = {1868-8969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10254},
doi = {10.4230/LIPIcs.STACS.2019.15},
annote = {Keywords: dial-a-ride on the line, elevator problem, online algorithms, competitive analysis, smartstart, competitive ratio}
}
|
Keywords: |
|
dial-a-ride on the line, elevator problem, online algorithms, competitive analysis, smartstart, competitive ratio |
|
Collection: |
|
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
12.03.2019 |
