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.

Abstract

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''.


Actions:
Download: [img] Postscript - Preprinted Version
Download (395Kb) | Preview
Download: [img] PDF - Preprinted Version
Download (178Kb) | Preview
Export as:
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
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/447