Fr, 20.07.2018, 10:45

Fr, 20.07.2018, 11:45
Improved upper bound for online Dial-a-Ride on the line
AG-Seminar Optimierung

Referent: Alexander Birx
Raum: S4|10 1

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 ratio 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 improve the best known upper bound of 3.41 [Krumke 2000] for open, non-preemptive online Dial-a-Ride on the line to 2.94, thus ruling out a competitive ratio of 3. The best known lower bound remains 2.04 [SODA 2017]. We obtain our result by tight analysis of the SmartStart algorithm [STACS 2000] that gives a tight result for the general, metric case.



Fachbereich Mathematik
Technische Universität Darmstadt

Schlossgartenstraße 7
64289 Darmstadt

A A A | Print Drucken | Impressum Impressum | Contact Kontakt
    zum Seitenanfangzum Seitenanfang