@inproceedings{1b62f9c289e64f0c877081f89a81598d,
title = "A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line",
abstract = "Online matching on a line involves matching an online stream of items of various sizes to stored items of various sizes, with the objective of minimizing the average discrepancy in size between matched items. The best previously known upper and lower bounds on the optimal deterministic competitive ratio are linear in the number of items, and constant, respectively. We show that online matching on a line is essentially equivalent to a particular search problem, that we call k-lost cows. We then obtain the first deterministic sub-linearly competitive algorithm for online matching on a line by giving such an algorithm for the k-lost cows problem.",
author = "Antonios Antoniadis and Neal Barcelo and Michael Nugent and Kirk Pruhs and Michele Scquizzato",
year = "2014",
doi = "10.1007/978-3-319-18263-6",
language = "English",
isbn = "978-3-319-18262-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "11--22",
editor = "Evripidis Bampis and Ola Svensson",
booktitle = "Approximation and Online Algorithms",
address = "Germany",
note = "12th International Workshop on Approximation and Online Algorithms, WAOA 2014, WAOA ; Conference date: 11-09-2014 Through 12-09-2014",
}