SIGACT News Online Algorithms Column 28
Rob van Stee · ACM SIGACT News · 2016
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.In Section 3, we give a bound in terms of the number of crossing lines in the matching produced by γ-wfa.In Section 4, we consider the concept of extended costs.In Section 5, we define multipliers and use them to derive a different (but still linear) upper bound on the competitive ratio of γ-wfa. SegmentsA free interval is a maximal interval on the line that does not contain any requests or servers.When γ-wfa matches a request r to some server, we will denote this server by s r and the interval (or edge) (r, s r ) or (s r , r) by E r .This interval is partitioned into a set of segments, one for each