Online matching on a line

Bernard Fuchs, Winfried Hochstättler, Walter Kern

Research output: Book/ReportReportProfessional

7 Citations (Scopus)
90 Downloads (Pure)


We prove a lower bound $\rho \geq 9.001$ for the 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
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages14
ISBN (Print)0169-2690
Publication statusPublished - 2003

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • IR-65860
  • EWI-3495
  • MSC-68Q25
  • MSC-68M20
  • METIS-213733

Cite this