An approximate solution algorithm for the one-dimensional online median problem

The online median problem consists in finding a sequence of incremental solutions of the k-median problem with k increasing. A particular case of the problem is considered: the clients and facilities are located on the real line. The best algorithm available for the one-dimensional case has competitive ratio 8. We give an improved 5.83-competitive algorithm.