Probabilistic Analysis of an Algorithm for the Uncapacitated Facility Location Problem on Unbounded Above Random Input Data

Abstract

We consider a Facility Location Problem in the case where an instances are unbounded above independent random variables with exponential and truncated normal distribution. A probabilistic analysis of the approximation algorithm with polynomial time complexity is presented. Explicit evaluations of the performance guarantees are obtained and sufficient conditions for the algorithm to be the asymptotically optimal are presented.

Keywords

• facility location problem
• probabilistic analysis
• polynomial approximation algorithm
• asymptotically optimal algorithm
• relative error
• failure probability

Introduction

was presented by Borovkov, A. [2] for Travel Salesman Problem. In order to characterize the quality of the solution produced by the algorithm on the random input are selected the relative error "n and failure probability n [4].

In this paper we consider a probabilistic analysis of algorithm for solving the Uncapacitated FLP on unbounded above random input data with the exponential and truncated normal distribution. We obtain estimates of the relative error, the failure probability of the algorithm and the sufficient conditions of asymptotic optimality of the algorithm. 1

Formulation of the Problem Consider the mathematical formulation of the Uncapacitated Facility Location Problem (UFLP) [3]:

L(X) = ∑ ci0xi + ∑ i2I i2I j2J ∑ cij xij ! min;

X ∑ xij = 1; j 2 J ; 0 i2I xij

xi; i 2 I; j 2 J ; xi 2 f0; 1g ; i 2 I; ( 1 ) ( 2 ) ( 3 ) ( 4 ) I = f1; 2; :::; mg is the set of the possible facility locations; J = f1; 2; :::; ng is the set of the demand points; ci0 is the the initial cost of the facility placing at location i; cij is the cost of servicing a demand point j by an open facility at location i; X = (xi)(xij ) is the solution of UFLP, where xi is a boolean variable indicates that facility at location i 2 I is open, xij indicates that open facility i 2 I servicing a demand point j 2 J .

The goal is to nd a set of facilities to open I~ I; I~ ̸= ∅ which allows to satisfy all of the demand points with a minimum total cost.

The problem ( 1 ){( 4 ) is N P -hard because it reduces to the Set Covering Problem [6].

In [8] is represented a polynomial approximation algorithm for solving the problem ( 1 ){( 4 ) from class K~mn(an; bn; a0n; b0 ) with elements of matrix (cij ); i 2 I; j 2 J n and vector (ci0); i 2 I; from intervals [an; bn] and [a0n; b0n]; an and b0n non-negative accordingly. Performance guarantees of the algorithm and conditions of asymptotic optimality are obtained when the elements of the matrix (cij ) is independent identically distributed random variables de ned on a limited interval with uniform distribution function F, where F( ) ; 0 1 for values ij = (cij an)=(bn an).

The work [9] devoted to the probabilistic analysis of several greedy approximation algorithms for UFLP with input data generated by choosing n random points in the unit square, where each point is represented as a demand point, as well as a possible facility location, i.e. sets I and J match. The authors proposed the conditions of asymptotic optimality for the problem with the same opening costs of the facilities: ci0 = n; i 2 I.

In this paper performed a probabilistic analysis of polynomial approximation algorithm for solving UFLP in a class of the K~nn(1; 1; b0n) under the following assumptions: 1) The locations of demand points and possible facility locations match: I = J and m = n.

2) The initial cost for opening facilities alike: ci0 = b0n; i 2 I.

3) Off-diagonal elements of the matrix (cij ) is independent identically distributed random variables from an unbounded above interval (bn = 1) with a lower limit, without loss of generality, equals to 1.

4) Probabilistic analysis is performed for two distribution functions: exponential with a parameter n and truncated normal distribution with parameter n.

As a result of the probabilistic analysis we obtain corresponding estimates of the relative error and the failure probability of the algorithm and present sufficient conditions for asymptotic optimality.

Further for convenience we will have to deal with the matrix (~cij ) which off-diagonal elements are de ned as c~ij = cij 1; i; j 2 J .

Obviously the objective function L(X) of the original problem is associated with the objective function F(X) the problem with shifted matrix (c~ij )

L(X) = n + F(X):

Denote

n = { n; in the case of exponential distribution;

2 n; in the case of truncated normal distribution:

2

Algorithm A~ in the Case of Exponential Distribution We describe an approximate algorithm A~ , modifying itself from work [8]:

1. Calculating the parameters m0 m~ by the formulas:

Next we assume that number of the points with open facilities does not exceed the number of the point where is no facilities, i.e. at least m~ < n=2. 2. Choosing a subset I~ J , consisting of the last m~ elements of the vector (ci0); i 2 J .

We assume J~ = J n I~, n~ = jJ~j. 3. Compute the vector of destinations (ij ); j 2 J~, where 4. As a result of the algorithm A~ choose solution X~ = (x~i)(x~ij ), where: ij = arg minfc~ij ji 2 I~g; j 2 J :

~ x~i = { 1; i 2 I;

~ 0; i 2= I~; x~ij = { 1; i = ij ;

0; i ̸= ij :

By issuance of the solution X~ and the objective function L~ = L(X~ ) algorithm A~ completes its work.

The complexity of the algorithm Ae is : O( m~n) [8].

3

Probabilistic Analysis of Algorithm A~ In the analysis of the algorithm we will use the following notions [4]: De nition 1. We say that the algorithm A has estimates "nA; nA in class Kn of minimization problems of dimension n if

P {fA > (1 + "nA)f } nA; where "nA is the relative error and nA is the failure probability of the algorithm A, f is the optimal solution and fA is the solution found by the algorithm A. there are some estimates "nA; nA for it such that "nA; nA ! 0 as n ! 1.

To prove the main theorem we use:

Theorem 1. Petrov, V. [5] Let X1; : : : ; Xn are independent random variables and for some positive constants T and hj ; j = 1; : : : ; n; such that for all t; 0 t T EetXj

e 12 hjt2 ; j = 1; : : : ; n: We set H = n ∑hj and S = j=1 n ∑Xj , then: j=1 PfS > xg { exp { 2xH2 } exp { xT } 2 0 x

HT; x > HT:

In the case of an exponential distribution with parameter off-diagonal elements of the matrix (c~ij ) is as follows: n, the density of the the corresponding distribution function is: Lemma 1. For the expectation and variance of the random variable 1 i m~ c~ij ; min where c~ij is independent random variables with the same distribution function F (x) = 1 e x= n ; 0 x 1, the following estimates are valid:

ECm~ = DCm~ = Proof. By calculating the vector of the destination at Step 3 of the algorithm A~ we chose minimum among of me independent random variables c~ij for a xed j 2 J~. Denote this random variable as j( m~) = 1miinm~ c~ij: The total cost of servicing obtained by the n~ algorithm A~ denote as Cm~ = ∑ j( m~).

j=1

By choosing the solutions X~ with algorithm A~ we have

The distribution function of a value j( m~) equal to

m~ n~ F~ = F(X~ ) = ∑ ci0 + ∑ i=1 j=1 j( m~) = m~b0n + Cm~ ; F ( j( m~)) = 1 (1

F (x))m~ : ∫1 x m~e x mn~ 0 n dx = ( 5 ) ( 6 ) ( 7 ) 1 ∫ 0 1 = xe xmn~ 1 + ∫ 0

e 0 E j( m~) = xm~ (1

F (x))m~ 1dF (x) = x mn~ dx = n e m~ xm~ 1 n 0 = n : m~

For the expectation of the value Cm~ we have:

Estimate the variance of the random variable Cm~ :

D j( m~) = E j( m~)2 (E j( m~))2 = x2(1

F (x))m~ 1dF (x) = 0 ∫1 x2 m~e x mn~ n dx

2 m~n~2 = x2e x m~ 1 n 0 + 2 1 ∫ 0 xe x mn~ dx

2 mn2 = 2 m~n2 = m~ 2 2 n : n~ ECm~ = ∑ E j( m~) = n~ n : j=1 m~ 1 ∫ 0 n~ DCm~ = ∑ D j( m~) = j=1 n~ n2 m~2 : Lemma 2. Algorithm A~ provides a solution such that for the objective function F~ valid the upper bounds: ~ F ~ F m~ n + (1 + "′n~ ) where "′n = √ln n=n ! 0; n ! 1.

Proof. Consider steps 2.2 and 2.3 of algorithm A~. From Lemma 1 and equation ( 7 ) follows ~ F

m~ n + n~ m~n = F^ F^′m~ = n n~ n m~2 We study the behavior of the objective function with respect to the point m0 = √n n= n. When m < m0 and "n = √ln n=n ! 0; n ! 1:

F~ = F(X~ ) = m~ ∑ ci0 + ∑ i=1 j2J~ 1 miinm~ cij = m~ n + Cm~ m~ n + nm~n = F^

We show with high probability

Actually,

~ F m~ n + (1 + "′n) n n = F^:

m~ PfF~ > m~ n + (1 + "′n)Cm~ g

PfCm~ > (1 + "′n)ECm~ g PfjCm~

ECm~ j > "′nECm~ g

DCm~ 1 ("′nECm~ )2 = ln n

From the mentioned above it is clear that with such select of the parameter m~ the upper bound of objective function F^ derived as the result of algorithm A~, for small "n, is close to its minimum value.

Lemma 3. [10] For non-negative real x and , 1 + x + x2 ex e( 0;5)x2 Theorem 2. Let the elements of service costs c~ij be an independent identically distributed random variables with values in the unbounded above interval [1; 1), having exponential or truncated normal distribution with parameters n or n. Algorithm A~ nds the solution with conditions of asymptotic optimality

(pn ) n = O ln n ; and with the relative error and the failure probability n = o (pn )

; ln n "nA = O ( 1 );

ln n nA = exp{ 3 }

n : 8 Lemma 4. Let X~j = j( m~), j = 1; : : : ; n~. Put T = 2m~n and hj = 3m~ 22n ; j = 1; : : : ; n~: Then, for every j = 1; : : : ; n~ and t, 0 t T , the following hold: ( 10 ) ( 11 ) ( 12 ) ( 13 ) n~ satisfy the Proof.

Eet(X~j EX~j) exp (hjt2 )

: 2 EetX~j = 1 ∫ 0

1 etxdF ( j( m~)) = ∫ m~ etxe xm~ = n dx =

n = m e(t m~= n)x 1 n t m~~= n 0 =

0 m= n m~= n t =

1 1 t n=m~ :

Because 0

t

T and T = 2m~n , then using Lemma 3, we have EetX~j =

1 1 t n= m~ = ∑1 ( t n )k

m~ k=0 = 1 + tm~n + tm22n2 ( 1 1 t n=m~ )

Thereby,

1 + tm~n + 2tm~2 2n2 Eet(X~j EX~j) exp (t n= m~) exp (1; 5t2 n2= m~2): exp (1; 5t2 n2= m~2) exp (hjt2=2):

Proof. Theorem 2.

From Lemma 4 follows that it variables X~j′ = X~j EX~j; 1 m~ conditions of the Petrov theorem.

n~ n~ Denote S = ∑X~j′ . Put T = 2m~n and H = ∑hj = 3nm~~ 22n , we have j=1 j=1

HT = 3n~ n : 2m~ ities F

Let us estimate the failure probability nA of algorithm A~ with the obvious inequaln~ and EF~ m~ n + EC m~ = E^F~: P{FA~ > (1 + "nA)F }

P{F~ + n~ > (1 + "nA)n~}

n~ P{m~ n + ∑ X~j > n~"nA} j=1 n~ P{∑ X~j > "nAn~ j=1 m~ n}

n~ P{∑ X~j′ > "nAn~ j=1 ( m~ n + n~m~n )}: ( 14 ) Since m0 m~ m0 + 1 and m0 = √ n nn , we have ( m~ n + n~ n ) m~ (m0 + 1) n + n~ n = 2√n~ n n + n m0 .

We extend inequality (14), by denoting "nAn~

(2pn~ n n + n) = 2 3lnnn : P{S > "nAn~(m~ n + n~m~n )g

P{S > "nAn~ 3n (2√n~ n n + n} = P{S > 2 ln n g: Furthermore, to hence also the relative error of the algorithm we obtain "nA =

3 2 ln n + 2 √ n n + n~ n~ n =

3 2 ln n + 2 √ n n + n~ n : n~

With the conditions on n and n we have

Because

( 1 ) "nA = O ln n

! 0 n ! 1: 3n~ n HT = 2m~ 3n n = 3=2√n n n 2m0

3n 2 ln n = x xT =

3n m~ 2 ln n 2 n

3n m0 = 2 ln n 2 n

3n 1 √ n 2 ln n 2 n 3n 4 ; by Petrov Theorem we have:

P fS > xg e x2T e 38n = n: So as "nA ! 0; nA ! 0 when n ! 1, algorithm A~ is asymptotically optimal. Thus, in the case of exponential distribution for independent identically distributed random variables c~ij holds Theorem 2, where n = n. 4.1

Case of the Truncated-Normal Distribution In the case of truncated normal law consider a symmetrical right half of the normal law with density parameter n for the off-diagonal elements of the matrix (c~ij ), having the following form: for the corresponding distribution function: De nition 2. [11] We say that the distribution function F1(x) majorizes the distribution function F2(x), if F1(x) > F2(x) for any x.

Lemma 5. [10] For any x 0 and

> 0 inequality holds ∫x √ 0 2 2 exp ( u2 )du 2 2 1 exp ( x )

: 2 Lemma 6. [11] Let 1; : : : ; ; m be an independent identically distributed random variables with the distribution function F (x), F^(x) is a function of random variable = 1 miinm i, let 1; : : : ; m be an independent identically distributed random variables with the distribution function G(x), G^(x) is function of random variable = min 1 i m i Lemma 7. [11] Let P ; P ; P ; P be a distribution functions of random variables ; ; ; accordingly and and be independent, and be independent. Then (8x P (x)

P (x)) ^ (8y P (y)

P (y)) ) (8z P + (z)

P + (z): Lemma 8. [11] Let the distribution function F (x) of the random value c~ij be such as F (x) F ′(x). Then for algorithm A~ hold the same performance guarantees ("nA; nA) in the case of input with the distribution function F ′(x).

Let F ′(x) = F (x) and F = G(x), from Lemmas 5 { 8 follows the validity of the Theorem 2 in the case of a truncated-normal distribution. 5

Conclusion

In this paper a probabilistic analysis of approximation algorithm A~ presented by using Petrov Theorem for Uncapacitated Facility Location Problem in the case when the matrix of the elements of the costs is an independent identically distributed variables from the unbounded above interval with exponential and truncated normal distribution.

The performance guarantees of the algorithm: the relative error and the failure probability and sufficient conditions for its asymptotic optimality are presented.

References

1. Mirchandani , P. , Francis , R. : (eds.) Discrete location theory . Wiley-Interscience Series in Discrete Mathematics and Optimization . Wiley, New York, 1990 .

2. Borovkov , A. : On probabilistic formulation of two economic problems . Doklady AN SSSR , 1962 , 146 ( 5 ), 983 {986(in Russian).

3. Beresnev , V. , Gimadi, Ed., Dementiev , V. : Extremal Problems of Standardization, Nauka, Moskow, 334 p., 1978 (in Russian)..

4. Gimadi, Ed., Glebov , N. , Perepelica , V. : Algorithms with bounds for discrete optimization problems , 31 , 35{ 42 , 1974 (in Russian).

5. Petrov V.V. : Limit Theorems of Probability Theory . Sequences of Independent Ran- dom Variables . Clarendon Press, Oxford, 304 p. ( 1995 )

6. Garey , M. , Johnson , D: Computers and Intractability; 1982 . - 416 p.

7. Chudak , F. : Improved approximation algorithms for uncapacitated facility location . In Integer programming and combinatorial optimization , 180 { 194 , 1998 .

8. Gimadi, Ed.: Aprior performance estimates of the approximation solving for the Problem of Standardization. Upravlyaemye sistemy , Novosibirsk, 1987 , 27 , 25{29(in Russian)

9. Flaxman , A. , Frieze , A. , Vera , J.: On average case performance of some greedy approximation algorithms for the uncapacitated facility location problem . Comb. Probab. Comput . 16 ( 05 ), 713 { 732 ( 2007 )

10. Gimadi , E.Kh. , Le Gallu , A. , and Shakhshneider , A.V. : Probabilistic Analysis of One Approximate Algorithm for the Traveling Salesman Problem with Unbounded Inputs, Diskret . Anal. Issled. Oper., 2008 , 15 ( 1 ), 23 { 43 .

11. Gimadi, Ed., Glazkov , Yu.: An asymptotically optimal algorithm for one modi cation of planar three-index assignment . Diskretn. Anal. Issled . Oper., Ser . 2 , 13 ( 1 ), 10 - 26 ( 2006 ).

12. Piersma , N.: A probabilistic analysis of the capacitated facility location problem . J. Comb. Optim . 1999 . 3 ( 1 ), 31 - 50 .

13. Angluin , D. , Valiant , L. : Fast probabilistic algorithm for Hamiltonian circuits and matchings . J. Comput. and System Sci . 1979 . 19 ( 2 ), 155 { 193 ( 1979 ).

14. Shmoys , D. , Tardos , E. , and Aardal , K. : Approximation algorithms for facility location problems . In Proc. 29th Annu. ACM Sympos. Theory Comput. , 265 { 274 ( 1997 ).

15. Guha , S. , Khuller , S. : Greedy strikes back: Improved facility location algorithms . In Proc of the 9th Annual ACM-SIAM Symp. on Discrete Algorithms , 649 { 657 ( 1998 ).