An approximation algorithm for the -level stochastic facility location problem
Introduction
The facility location problem (FLP) has been widely investigated in the area of operations research. This problem is NP-hard, and hence the focus has been on designing approximation algorithms with good performance. On the negative side, the approximation ratio for the FLP is at least 1.463 [8] unless P=NP. On the positive side, starting from the first constant ratio of 3.16 [15], approximation ratios have been improved steadily over the years, including in [6], [9], [10], [12], with the currently best ratio being 1.50 [4]. Many variants of the FLP have also been introduced in the literature (e.g. [3], [5], [16], [17], [18], [21], [23]). The current work is particularly relevant to one of these variants, namely, the -level facility location problem (-FLP). In this problem, each client must be severed by an open path along level sets of facilities. Approximation algorithms have also been proposed for solving this problem in the literature with the currently best ratio of 3 [1] being achieved by the (non-combinatorial) LP rounding technique, and a relatively poor combinatorial ratio of 3.27 [2]. For the special case of 2-FLP, a better non-combinatorial 1.77-approximation algorithm exists [22]. A new LP rounding 3-approximation algorithm for the -FLP is proposed by using a linear program which has a polynomial number of variables and constraints [7].
The stochastic facility location problem (SFLP) considers the stochastic version of the standard FLP by assuming the demands are stochastic. This problem was first introduced by Ravi and Sinha [13], who present a (non-combinatorial) LP rounding 8-approximation algorithm. The currently best ratio for the SFLP is 1.86 [20]. Further results related to SFLP are given in [11], [14], [19].
In this paper, we extend the above -FLP and SFLP to a new problem, called the -level stochastic facility location problem (-SFLP). Our main contribution is a 3-approximation algorithm. To achieve this result, a novel integer linear programming formulation is introduced for the problem by exploring the underlying stochastic structure. Then, integrated with the techniques of [1], [13], this new formulation leads to the desired result. Since there exists a combinatorial 3.27-approximation algorithm for the -FLP [2], it will be interesting to develop combinatorial approximation algorithms for the -SFLP.
Section snippets
The -level stochastic facility location problem
Let the set of all possible clients be . Each client must be assigned to precisely one facility at each of the levels. Let be the set of sites where facilities on level () are located, and assume that the sets are pairwise disjoint. Define . The cost of shipping between site and client is equal to which is metric (that is, satisfying symmetry, nonnegativity, and the triangle inequality). We use to denote a sequence of facilities, where
The algorithm
Let and be the optimal solutions to the primal and dual linear programs, respectively. Then
Define
Acknowledgements
The authors are grateful to Qin Wang and the area editor, both of whom offered insightful suggestions for improving the paper. The research of the first author is supported by Beijing Natural Science Foundation (No. 1102001). The second author’s research is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant 283103. The fourth author’s research is supported by NSF of China (No. 60773185) and PHR (IHLB).
References (23)
- et al.
A 3-approximation algorithm for the -level uncapacitated facility location problem
Information Processing Letters
(1999) - et al.
A new approximation algorithm for the multilevel facility location problem
Discrete Applied Mathematics
(2010) - et al.
Greedy strike back: improved facility location algorithms
Journal of Algorithms
(1999) A new approximation algorithm for the -facility location problem
Theoretical Computer Science
(2007)- et al.
Improved combinatorial approximation algorithms for the -level facility location problem
SIAM Journal on Discrete Mathematics
(2004) - A.F. Bumb, W. Kern, A simple dual ascent algorithm for the multilevel facility location problem, in: Proceedings of the...
- et al.
An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
SIAM Journal on Computing
(2010) - et al.
Approximation algorithms for soft-capacitated facility location in capacitated network design
Algorithmica
(2007) - et al.
Improved approximation algorithms for the uncapacitated facility location problem
SIAM Journal on Computing
(2003) - et al.
Greedy facility location algorithm analyzed using dual fitting with factor-revealing LP
Journal of the ACM
(2003)
Approximation algorithms for metric facility location and -median problems using the primal–dual schema and Lagrangian relaxation
Journal of the ACM
Cited by (11)
Linear and piecewise linear formulations for a hierarchical facility location and sizing problem
2023, Omega (United Kingdom)Multi-level facility location problems
2018, European Journal of Operational ResearchPrimal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach
2015, Theoretical Computer ScienceCitation Excerpt :As a demonstration, we extend our primal–dual algorithm to several variants of the 2-LFLP. These variants have been investigated in the literature for either 1-LFLP or k-LFLP, including the stochastic 1-LFLP and k-LFLP [18,20,27] for which the resultant primal–dual algorithm offers an improved approximation ratio; and the dynamic 1-LFLP [28] and the 1-LFLP with linear-cost [19] for which the resultant primal–dual algorithms lead to the first constant approximation ratios. We present the main idea of the algorithm in Section 3.1 before we offer the formal description, an illustrative example, and the approximation ratio analysis of the primal–dual algorithm in Sections 3.2, 3.3, and 3.4, respectively.
Hierarchical facility location problem: Models, classifications, techniques, and applications
2014, Computers and Industrial EngineeringApproximation algorithms for k-level stochastic facility location problems
2017, Journal of Combinatorial Optimization