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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ascheuer, N., Krumke, S.O., Rambau, J.: Online dial-a-ride problems: Minimizing the completion time. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 639–650. Springer, Heidelberg (2000)
Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M.: Algorithms for the on-line traveling salesman. Algorithmica 29(4), 560–581 (2001)
Blom, M., Krumke, S.O., de Paepe, W.E., Stougie, L.: The online-TSP against fair adversaries. Informs Journal on Computing 13(2), 138–148 (2001); In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, pp. 137–148. Springer, Heidelberg (2000) (a preliminary version appeared)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
de Paepe, W.E., Lenstra, J.K., Sgall, J., Sitters, R.A., Stougie, L.: Computer-aided complexity classification of dial-a-ride problems. Informs Journal on Computing (to appear, 2003)
Feuerstein, E., Stougie, L.: On-line single server dial-a-ride problems. Theoretical Computer Science 268(1), 91–105 (2001)
Grötschel, M., Krumke, S.O., Rambau, J. (eds.): Online Optimization of Large Scale Systems. Springer, Heidelberg (2001)
Hauptmeier, D., Krumke, S.O., Rambau, J.: The online dial-a-ride problem under reasonable load. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, pp. 125–136. Springer, Heidelberg (2000)
Irani, S., Lu, X., Regan, A.: On-line algorithms for the dynamic traveling repair problem. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 517–524 (2002)
Krumke, S.O.: Online Optimization: Competitive Analysis and Beyond. Habilitationsschrift, Technische Universität Berlin (2002)
Krumke, S.O., de Paepe, W.E., Poensgen, D., Stougie, L.: News from the online traveling repairman. Theoretical Computer Science 295(1–3), 279–294 (2003); In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, p. 487–581. Springer, Heidelberg (2001) (a preliminary version appeared)
Krumke, S.O., Laura, L., Lipmann, M., Marchetti-Spaccamela, A., de Paepe, W.E., Poensgen, D., Stougie, L.: Non-abusiveness helps: An \(\mathcal O(1)\)-competitive algorithm for minimizing the maximum flow time in the online traveling salesman problem. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 200–214. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krumke, S.O., de Paepe, W.E., Poensgen, D., Lipmann, M., Marchetti-Spaccamela, A., Stougie, L. (2006). On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem. In: Erlebach, T., Persinao, G. (eds) Approximation and Online Algorithms. WAOA 2005. Lecture Notes in Computer Science, vol 3879. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11671411_20
Download citation
DOI: https://doi.org/10.1007/11671411_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32207-8
Online ISBN: 978-3-540-32208-5
eBook Packages: Computer ScienceComputer Science (R0)