Optimization Online


Approximating the Two-Level Facility Location Problem Via a Quasi-Greedy Approach

Jiawei Zhang (jiazhang***at***stanford.edu)

Abstract: We propose a {\em quasi-greedy} algorithm for approximating the classical uncapacitated $2$-level facility location problem ($2$-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization $2$-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of our algorithm is that it combines the technique of randomized rounding with that of dual fitting. This new approach enables us to approximate the metric $2$-LFLP in polynomial time with a ratio of $1.77$, a significant improvement on the previously known approximation ratios. Moreover, our approach results in a local improvement procedure for the $2$-LFLP, which is useful in improving the approximation guarantees for several other multi-level facility location problems. An additional result of our approach is an $O(\ln(n))$-approximation algorithm for the non-metric $2$-LFLP, where $n$ is the number of clients. This is the first non-trivial approximation for a non-metric multi-level facility location problem.

Keywords: two-level facility location problem, approximation algorithm, quais-greedy approach

Category 1: Combinatorial Optimization (Approximation Algorithms )

Citation: Working Paper, Department of Management Science and Engineering, Stanford University, July, 2003. An extended abstract of this paper is to appear in the Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2004.

Download: [Postscript][PDF]

Entry Submitted: 07/02/2003
Entry Accepted: 07/03/2003
Entry Last Modified: 10/04/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society