On minimizing the maximum flow time in the online dial-a-ride problem

In: The 3rd Workshop on on Approximation and Online Algorithms. Lecture Notes in Computer Science, Volume 3879, Springer, P. 258--269, 2005

Authors

• Sven O. Krumke
• Willem E. de Paepe
• Diana Poensgen
• Maarten Lipmann
• Alberto Marchetti-Spaccamela

Abstract

In the online dial-a-ride problem (OlDarp), objects must be transported by a server between points in a metric space. Transportation requests ("rides") arrive online, specifying the objects to be transported and the corresponding source and destination. We investigate the OlDarp for the objective of minimizing the maximum flow time. It has been well known that there can be no strictly competitive online algorithm for this objective and no competitive algorithm at all on unbounded metric spaces. However, the question whether on metric spaces with bounded diameter there are competitive algorithms if one allows an additive constant in the definition competitive ratio, had been open for quite a while. We provide a negative answer to this question already on the uniform metric space with three points. Our negative result is complemented by a strictly 2-competitive algorithm for the Online Traveling Salesman Problem on the uniform metric space, a special case of the problem.

BibTeX

 
@InProceedings{ KrumkeEtAl:OnlineDial, 
   title = { On minimizing the maximum flow time in the online dial-a-ride problem }, 
   author = { Sven O. Krumke and Willem E. de Paepe and Diana Poensgen and Maarten Lipmann and Alberto Marchetti-Spaccamela },   
   booktitle = { The 3rd Workshop on on Approximation and Online Algorithms },  
   series = { Lecture Notes in Computer Science }, 
   volume = { 3879 },     
   publisher = { Springer },   
   pages = { 258--269 },   
   year = 2005, 
} 

---

This publication belongs to the project DeNDeMA.