Online matching on a line

Bernard Fuchs, Winfried Hochstättler, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

23 Citations (Scopus)

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.
Original languageUndefined
Pages (from-to)251-264
Number of pages13
JournalTheoretical computer science
Volume332
Issue number1-3
DOIs
Publication statusPublished - 2005

Keywords

  • Competitive Analysis
  • On-line algorithms
  • METIS-225533
  • IR-77417
  • Matching

Cite this