On the Advice Complexity of Online Matching on the Line

We consider the weighted matching problem on the line with advice complexity. We give a 1-competitive online algorithm with advice complexity $n-1,$ and show that there is no 1-competitive online algorithm reading less than $n-1$ bits of advice. Moreover, we present a weakly $c(n/k)$-competitive online algorithm with advice complexity O(k(log N + log n)) where n is the number of servers, N is the distance of the minimal and maximal servers, and $c(n)$ is the complexity of the best online algorithm without advice.