Search Results

Documents authored by Birx, Alexander

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.21
Improved Bounds for Open Online Dial-a-Ride on the Line

Authors: Alexander Birx, Yann Disser, and Kevin Schewior

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a lower bound of 2.0585 on the competitive ratio, which is the first bound that strictly separates online Dial-a-Ride on the line from online TSP on the line in terms of competitive analysis, and is the best currently known lower bound even for general metric spaces. On the other hand, we present an algorithm that improves the best known upper bound from 2.9377 to 2.6662. The analysis of our algorithm is tight.
Cite as

Alexander Birx, Yann Disser, and Kevin Schewior. Improved Bounds for Open Online Dial-a-Ride on the Line. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{birx_et_al:LIPIcs.APPROX-RANDOM.2019.21,
  author =	{Birx, Alexander and Disser, Yann and Schewior, Kevin},
  title =	{{Improved Bounds for Open Online Dial-a-Ride on the Line}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.21},
  URN =		{urn:nbn:de:0030-drops-112367},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.21},
  annote =	{Keywords: dial-a-ride on the line, elevator problem, online algorithms, competitive analysis, smartstart, competitive ratio}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.15
Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line

Authors: Alexander Birx and Yann Disser

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

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.
Cite as

Alexander Birx and Yann Disser. Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{birx_et_al:LIPIcs.STACS.2019.15,
  author =	{Birx, Alexander and Disser, Yann},
  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 =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.15},
  URN =		{urn:nbn:de:0030-drops-102543},
  doi =		{10.4230/LIPIcs.STACS.2019.15},
  annote =	{Keywords: dial-a-ride on the line, elevator problem, online algorithms, competitive analysis, smartstart, competitive ratio}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact