A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms
Subtitle of host publication12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers
EditorsEvripidis Bampis, Ola Svensson
Place of PublicationCham
PublisherSpringer
Pages11-22
ISBN (Electronic)978-3-319-18263-6
ISBN (Print)978-3-319-18262-9
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event12th International Workshop on Approximation and Online Algorithms, WAOA 2014 - Wrocław, Poland
Duration: 11 Sep 201412 Sep 2014
Conference number: 12

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8952
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameTheoretical Computer Science and General Issues
PublisherSpringer

Conference

Conference12th International Workshop on Approximation and Online Algorithms, WAOA 2014
Abbreviated titleWAOA
CountryPoland
CityWrocław
Period11/09/1412/09/14

Cite this