Birx, Alexander ; Disser, Yann ; Schewior, Kevin
Hrsg.: 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
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (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.
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2019 |
| Herausgeber: | Achlioptas, Dimitris ; Végh, László |
| Autor(en): | Birx, Alexander ; Disser, Yann ; Schewior, Kevin |
| Art des Eintrags: | Bibliographie |
| Titel: | Improved Bounds for Open Online Dial-a-Ride on the Line |
| Sprache: | Englisch |
| Publikationsjahr: | 17 September 2019 |
| Verlag: | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Buchtitel: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |
| Reihe: | Leibniz International Proceedings in Informatics |
| Band einer Reihe: | 145 |
| Veranstaltungstitel: | 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX/RANDOM 2019) |
| Veranstaltungsort: | Cambridge, USA |
| Veranstaltungsdatum: | 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... |
| Kurzbeschreibung (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. |
| Fachbereich(e)/-gebiet(e): | Exzellenzinitiative Exzellenzinitiative > Graduiertenschulen Exzellenzinitiative > Graduiertenschulen > Graduate School of Computational Engineering (CE) 04 Fachbereich Mathematik 04 Fachbereich Mathematik > Optimierung 04 Fachbereich Mathematik > Optimierung > Discrete Optimization |
| Hinterlegungsdatum: | 25 Aug 2020 07:38 |
| Letzte Änderung: | 18 Aug 2022 09:23 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum