Online matching on a line

Bernard Fuchs; Winfried Hochstättler; Walter Kern

doi:10.1016/j.tcs.2004.10.028

Online matching on a line

Bernard Fuchs, Winfried Hochstättler, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

34 Citations (Scopus)

5 Downloads (Pure)

Abstract

Given a set S c R of points on the line, we consider the task of matching a sequence (r1,r2,…) of requests in R to points in S. It has been conjectured [Online Algorithms: The State of the Art, Lecture Notes in Computer Science, Vol. 1442, Springer, Berlin, 1998, pp. 268–280] that there exists a 9-competitive online algorithm for this problem, similar to the so-called “cow path” problem [Inform. and Comput. 106 (1993) 234–252]. We disprove this conjecture and show that no online algorithm can achieve a competitive ratio strictly less than 9.001. Our argument is based on a new proof for the optimality of the competitive ratio 9 for the “cow path” problem.

Original language	Undefined
Pages (from-to)	251-264
Number of pages	13
Journal	Theoretical computer science
Volume	332
Issue number	1-3
DOIs	https://doi.org/10.1016/j.tcs.2004.10.028
Publication status	Published - 2005

Keywords

Competitive Analysis
On-line algorithms
METIS-225533
IR-77417
Matching

Access to Document

10.1016/j.tcs.2004.10.028

Cite this

@article{d272465a18fb4ee08898a4ef11c090d3,

title = "Online matching on a line",

abstract = "Given a set S c R of points on the line, we consider the task of matching a sequence (r1,r2,…) of requests in R to points in S. It has been conjectured [Online Algorithms: The State of the Art, Lecture Notes in Computer Science, Vol. 1442, Springer, Berlin, 1998, pp. 268–280] that there exists a 9-competitive online algorithm for this problem, similar to the so-called “cow path” problem [Inform. and Comput. 106 (1993) 234–252]. We disprove this conjecture and show that no online algorithm can achieve a competitive ratio strictly less than 9.001. Our argument is based on a new proof for the optimality of the competitive ratio 9 for the “cow path” problem.",

keywords = "Competitive Analysis, On-line algorithms, METIS-225533, IR-77417, Matching",

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

year = "2005",

doi = "10.1016/j.tcs.2004.10.028",

language = "Undefined",

volume = "332",

pages = "251--264",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Online matching on a line

AU - Fuchs, Bernard

AU - Hochstättler, Winfried

AU - Kern, Walter

PY - 2005

Y1 - 2005

N2 - Given a set S c R of points on the line, we consider the task of matching a sequence (r1,r2,…) of requests in R to points in S. It has been conjectured [Online Algorithms: The State of the Art, Lecture Notes in Computer Science, Vol. 1442, Springer, Berlin, 1998, pp. 268–280] that there exists a 9-competitive online algorithm for this problem, similar to the so-called “cow path” problem [Inform. and Comput. 106 (1993) 234–252]. We disprove this conjecture and show that no online algorithm can achieve a competitive ratio strictly less than 9.001. Our argument is based on a new proof for the optimality of the competitive ratio 9 for the “cow path” problem.

AB - Given a set S c R of points on the line, we consider the task of matching a sequence (r1,r2,…) of requests in R to points in S. It has been conjectured [Online Algorithms: The State of the Art, Lecture Notes in Computer Science, Vol. 1442, Springer, Berlin, 1998, pp. 268–280] that there exists a 9-competitive online algorithm for this problem, similar to the so-called “cow path” problem [Inform. and Comput. 106 (1993) 234–252]. We disprove this conjecture and show that no online algorithm can achieve a competitive ratio strictly less than 9.001. Our argument is based on a new proof for the optimality of the competitive ratio 9 for the “cow path” problem.

KW - Competitive Analysis

KW - On-line algorithms

KW - METIS-225533

KW - IR-77417

KW - Matching

U2 - 10.1016/j.tcs.2004.10.028

DO - 10.1016/j.tcs.2004.10.028

M3 - Article

SN - 0304-3975

VL - 332

SP - 251

EP - 264

JO - Theoretical computer science

JF - Theoretical computer science

IS - 1-3

ER -