| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 431734 | Journal of Discrete Algorithms | 2007 | 8 Pages |
Abstract
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).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dimitris Fotakis,