Paper Info
Title
On minimizing the maximum flow time in the online dial-a-ride problem
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.
Year
DOI
Venue
2005
10.1007/11671411_20
Mathematical Programming
Keywords
Field
DocType
competitive algorithm,maximum flow time,online dial-a-ride problem,definition competitive ratio,metric space,uniform metric space,negative result,unbounded metric space,competitive online algorithm,negative answer,2-competitive algorithm,maximum flow,generic algorithm,online algorithm,traveling salesman problem,competitive ratio
Online algorithm,Mathematical optimization,Computer science,Convex metric space,K-server problem,Metric (mathematics),Algorithm,Intrinsic metric,Travelling salesman problem,Metric space,Competitive analysis
Conference
Volume
ISSN
ISBN
3879
0302-9743
3-540-32207-8
Citations 
PageRank 
References 
2
0.37
10
Authors
6
Name
Order
Citations
PageRank
Sven O. Krumke130836.62
Willem E. de Paepe21179.74
Diana Poensgen3314.48
Maarten Lipmann4344.65
Alberto Marchetti-Spaccamela51584150.60
Leen Stougie6892107.93