SIGACT News Online Algorithms Column 27
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 paper [3] which has never appeared in a journal.I have expanded the proofs and slightly reorganized the presentation.This column contains a proof of a linear upper bound for the generalized work function algorithm and a logarithmic lower bound for the algorithm.A later column will give a more detailed analysis of this algorithm, leading to a more precise (but still linear) upper bound.I conjecture that this algorithm in fact has a logarithmic competitive ratio (which would match the known lower bound for it), but this remains an open question.We generalize this result in the next lemma.where we have used ( 6) and ( 7) in the penultimate line.This means that the lemma also holds for any x ∈ [s, s 2 ), from the induction hypothesis for the balanced interval (s, s 2 ) (which has fewer requests).Now suppose x ∈ [r, s).Before request r arrived, (s 1 , s) was a balanced interval.Hence by the second part of the induction hypothesis, we havewhere we have used ||B -(A, R) ∩ [x, s]|| = s -x -||B + (A , R ) ∩ [x, s]||.Summing (8) and (9) we get 2γ||B -(A, R) ∩ [s 1 , x]|| ≤ (γ + 1)d(s 1 , x) -2d(r, x)and the lemma follows.