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.APPROX-RANDOM.2019.21
URN: urn:nbn:de:0030-drops-112367
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11236/
Go to the corresponding LIPIcs Volume Portal

Birx, Alexander ; Disser, Yann ; Schewior, Kevin

Improved Bounds for Open Online Dial-a-Ride on the Line

pdf-format:
LIPIcs-APPROX-RANDOM-2019-21.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{birx_et_al:LIPIcs:2019:11236,
  author =	{Alexander Birx and Yann Disser and Kevin Schewior},
  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 =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11236},
  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}
}

Keywords: dial-a-ride on the line, elevator problem, online algorithms, competitive analysis, smartstart, competitive ratio
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI