Please use this identifier to cite or link to this item:
Title: SIGACT News Online Algorithms Column 28: Online Matching on the Line, Part 2
Authors: Van Stee, Rob
First Published: 2-Jun-2016
Publisher: Association for Computing Machinery
Citation: SIGACT News, 2016, 47 (2), pp. 40-51
Abstract: In the online matching problem on the line, requests (points in R) arrive one by one to be served by a given set of servers. Each server can be used only once. This is a variant of the k-server problem restricted to the real line. Although easy to state, this problem is stil wide open. The best known lower bound is 9.001 [2], showing that this problem is really different from the well-known cow path problem. Antoniadis et al. [1] recently presented a sublinearly competitive algorithm. In this column, I present some results by Elias Koutsoupias and Akash Nanavati on this problem with kind permission of the authors. The column is based on Akash’ PhD thesis [4], which contains an extended version of their joint WAOA 2003 paper [3] which has never appeared in a journal. I have expanded the proofs and slightly reorganized the presentation. The previous column (see SIGACT News 47(1):99-111) contains a proof of a linear upper bound for the generalized work function algorithm and a logarithmic lower bound for the algorithm. This column gives a more detailed analysis of this algorithm, leading to a different (but again linear) upper bound. The techniques used here may potentially be helpful to show a sublinear upper bound for γ-wfa. I conjecture that this algorithm in fact has a logarithmic competitive ratio (which would match the known lower bound for it), but this very much remains an open question.
DOI Link: 10.1145/2951860.2951871
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © the authors, 2016. This version of the article is distributed under the terms of the Creative Commons Attribution-Non Commercial-No Derivatives License ( ), which permits use and distribution in any medium, provided the original work is properly cited, the use is non-commercial and no modifications or adaptations are made.
Description: The final published version is available through the links above.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
sigact28revised.pdfPost-review (final submitted author manuscript)771.13 kBUnknownView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.