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 |
Options (only for editors)
Show editorial Details |