Online Matching On a Line

Bernard Fuchs, Winfried Hochstättler, Walter Kern

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

Abstract

We prove a lower bound ρ ≥ 9.001 for the i competitive ratio of the so-called online matching problem on a line. As a consequence, the online matching problem is revealed to be strictly more difficult than the “cow problem”.
Original languageUndefined
Title of host publication2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization
EditorsHaitze J. Broersma, U. Faigle, Johann L. Hurink, Stefan Pickl, Gerhard Woeginger
PublisherElsevier
Pages49-51
DOIs
Publication statusPublished - 2003
Event2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2003 - University of Twente, Enschede, Netherlands
Duration: 14 May 200316 May 2003

Publication series

NameElectronic Notes in Theoretical Computer Science (ENTCS)
PublisherElsevier
Volume13
ISSN (Print)1571-0661

Workshop

Workshop2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2003
Abbreviated titleCTW
CountryNetherlands
CityEnschede
Period14/05/0316/05/03

Keywords

  • IR-75418
  • Competitive Analysis
  • Matching
  • On-line algorithms

Cite this

Fuchs, B., Hochstättler, W., & Kern, W. (2003). Online Matching On a Line. In H. J. Broersma, U. Faigle, J. L. Hurink, S. Pickl, & G. Woeginger (Eds.), 2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization (pp. 49-51). (Electronic Notes in Theoretical Computer Science (ENTCS); Vol. 13). Elsevier. https://doi.org/10.1016/S1571-0653(04)00436-6