TU Darmstadt / ULB / TUbiblio

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

Birx, Alexander ; Disser, Yann ; Schewior, Kevin
eds.: Achlioptas, Dimitris ; Végh‬, ‪László (2019)
Improved Bounds for Open Online Dial-a-Ride on the Line.
22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX/RANDOM 2019). Cambridge, USA (20.09.2019-22.09.2019)
doi: 10.4230/LIPIcs.APPROX-RANDOM.2019.21
Conference or Workshop Item, Bibliographie

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.

Item Type: Conference or Workshop Item
Erschienen: 2019
Editors: Achlioptas, Dimitris ; Végh‬, ‪László
Creators: Birx, Alexander ; Disser, Yann ; Schewior, Kevin
Type of entry: Bibliographie
Title: Improved Bounds for Open Online Dial-a-Ride on the Line
Language: English
Date: 17 September 2019
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Book Title: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Series: Leibniz International Proceedings in Informatics
Series Volume: 145
Event Title: 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX/RANDOM 2019)
Event Location: Cambridge, USA
Event Dates: 20.09.2019-22.09.2019
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.21
URL / URN: https://drops.dagstuhl.de/opus/portals/lipics/index.php?semn...
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.

Divisions: Exzellenzinitiative
Exzellenzinitiative > Graduate Schools
Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
04 Department of Mathematics
04 Department of Mathematics > Optimization
04 Department of Mathematics > Optimization > Discrete Optimization
Date Deposited: 25 Aug 2020 07:38
Last Modified: 18 Aug 2022 09:23
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details