Online matching on a line

Fuchs, Bernard and Hochstättler, Winfried and Kern, Walter (2005) Online matching on a line. Theoretical Computer Science, 332 (1-3). pp. 251-264. ISSN 0304-3975

PDF
Restricted to UT campus only: Request a copy
219Kb

Abstract:	Given a set S c R of points on the line, we consider the task of matching a sequence (r1,r2,…) of requests in R to points in S. It has been conjectured [Online Algorithms: The State of the Art, Lecture Notes in Computer Science, Vol. 1442, Springer, Berlin, 1998, pp. 268–280] that there exists a 9-competitive online algorithm for this problem, similar to the so-called “cow path” problem [Inform. and Comput. 106 (1993) 234–252]. We disprove this conjecture and show that no online algorithm can achieve a competitive ratio strictly less than 9.001. Our argument is based on a new proof for the optimality of the competitive ratio 9 for the “cow path” problem.
Item Type:	Article
Copyright:	© 2005 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/77417
Official URL:	http://dx.doi.org/10.1016/j.tcs.2004.10.028
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 225533