A primal-dual algorithm for online non-uniform facility location

In the online version of Facility Location, the demand points arrive one at a time and must be irrevocably assigned to an open facility upon arrival. The objective is to minimize the sum of facility and assignment costs. We present a simple deterministic primal-dual algorithm for the general case of non-uniform facility costs. We prove that its competitive ratio is no greater than 4log(n+1)+24log(n+1)+2, which is close to the lower bound of Ω(lognloglogn).