Online matching on a line

Fuchs, Bernhard and Hochstättler, Winfried and Kern, Walter (2005) Online matching on a line.
Published in: Theoretical Computer Science Vol. 332 (1-3). pp. 251-264.


We prove a lower bound of 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''.

Download: [img] Postscript - Preprinted Version
Download (404kB) | Preview
Download: [img] PDF - Preprinted Version
Download (182kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2003-447
Depositing User: Bernhard Fuchs
Date Deposited: 22 Feb 2005 00:00
Last Modified: 19 Dec 2011 09:44