Memoryless facility location in one pass
Dimitris A. Fotakis · ACM Transactions on Algorithms · 2011
We present the first one-pass memoryless algorithm for metric Facility Location that maintains a set of facilities approximating the optimal facility configuration within a constant factor. The algorithm is randomized and very simple to state and implement. It processes the demand points one-by-one as they arrive, and keeps in memory only the facility locations currently open. We prove that its competitive ratio is less than 14 in the special case of uniform facility costs, and less than 49 in the general case of nonuniform facility costs.