Online matching on a line

Bernard Fuchs, Winfried Hochstättler, Walter Kern

Research output: Book/ReportReportProfessional

6 Citations (Scopus)
26 Downloads (Pure)

Abstract

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
No.1675
ISSN (Print)0169-2690

Keywords

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

Cite this