Online matching on a line

Bernard Fuchs; Winfried Hochstättler; Walter Kern

Online matching on a line

Bernard Fuchs, Winfried Hochstättler, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Book/Report › Report › Professional

6 Citations (Scopus)

46 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 language	Undefined
Place of Publication	Enschede
Publisher	University of Twente
Number of pages	14
ISBN (Print)	0169-2690
Publication status	Published - 2003

Publication series

Name	Memorandum Afdeling TW
Publisher	Department of Applied Mathematics, University of Twente
No.	1675
ISSN (Print)	0169-2690

Keywords

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

Access to Document

Cite this

@book{5727f84b820f426ca1e44a18480b2792,

title = "Online matching on a line",

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

keywords = "IR-65860, EWI-3495, MSC-68Q25, MSC-68M20, METIS-213733",

author = "Bernard Fuchs and Winfried Hochst{\"a}ttler and Walter Kern",

note = "Imported from MEMORANDA",

year = "2003",

language = "Undefined",

isbn = "0169-2690",

series = "Memorandum Afdeling TW",

publisher = "University of Twente",

number = "1675",

address = "Netherlands",

}

TY - BOOK

T1 - Online matching on a line

AU - Fuchs, Bernard

AU - Hochstättler, Winfried

AU - Kern, Walter

N1 - Imported from MEMORANDA

PY - 2003

Y1 - 2003

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

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

KW - IR-65860

KW - EWI-3495

KW - MSC-68Q25

KW - MSC-68M20

KW - METIS-213733

M3 - Report

SN - 0169-2690

T3 - Memorandum Afdeling TW

BT - Online matching on a line

PB - University of Twente

CY - Enschede

ER -