Complexities And Approximation Algorithms For Facility Location And K-Median Problems

The objective of discrete location problem is to identify a subset of facilities in the given set to serve some clients such that the total service cost is minimized. In the class of problems facility location (uncapacitated facility location), abbreviation for UFL, and k-median are the two most representative problems. Due to defining the cost for each facility and connection cost between a client and a facility, the UFL problem is to identify a subset of facilities and connect each client to a facility in it such that the sum of total cost of facilities associated with that subset of facilities and the total connection cost is minimized, while the k-median problem only requires that the total connection cost be minimized but the size of subset of facilities be at most k. The two problems have applications in the fields of region planning, management science, communication and computer science, such as the location and construction for communal facilities, the layout of logistics centers, location of telecom base stations and network route problem.UFL and k-median problems stem from a discussion in 1620. At that time bourgeois investors considered to select a proper position to build a manufactory around the existing production bases of raw materials, satisfying their respective output requirements of raw materials as well as minimizing the transport costs. After the discussion, Fermat-Weber problem as to how to select a center for some discrete points was formally proposed. It is also the rudiments of UFL and k-median problems. In 1963 UFL problem was formally proposed by Cooper. Next year, Hakimi formally proposed k-median problem and proved the two problems are NP-hard. Since then researchers in operations research and computer science studied them very well. They analyzed the two problems by various methods and attempted to find an effective method to obtain the near-optimal solutions to them. During the process of research last forty years, one has made significant and impressive advances in which the results of approximation algorithms are particularly remarkable.For UFL problem, the first constant factor approximation algorithm was given by Shmoys et al. The algorithm is based on LP-rounding and the filtering technique proposed by Lin and Vitter and achieves an approximation factor of 3.16. Their algorithm was improved by Guha and Khuller to 2.408 using a greedy augmentation procedure. In the literature[30], according to the hypothesis of P≠NP, the 1.463 inapproximability proof for UFL problem was also proposed. Later, Chudak and Shmoys gave an 1.736-approximation algorithm for UFL problem using LP-rounding technique. In 2002 Mahdian et al. showed that the greedy augmentation procedure together with cost scaling can be used to design 1.52-approximaton algorithm for UFL problem, which is the best-known factor.For k-median problem, the first constant factor approximation algorithm was given by Charikar et al. in 1999 using LP technique and achieving an approximation factor of 62/3. At the same year, Jain andVazirani gave an algorithm with approximation factor of 6 using LP and Primal-Dual method. Their result was improved by Charikar and Guha to 4 using greedy augmentation procedure and cost scaling technique. The best-known result for k-median problem is the (3+ε)-approximation algorithm given by Arya , based on a simple heuristic local search procedure.Reviewing research on the two problems in the past forty years, we take notice of the fact that one paid more attention to the approximation algorithm study of UFL and k-median problems in metric space, in which the connection costs between clients and facilities satisfy the triangle inequality. However, in the context of real world, the connection costs in many application models concerning the two problems may not always satisfy the constraint condition above. For the problems in which the connection costs needn't satisfy the triangle inequality, we denote them as the UFL and k-median problems in general (non-metric) distance space, respectively. Such problems have been referred to in the dynamic routing algorithm of communication network in cooperative research between HP Corporation and British Telecom.Compared with results of UFL and k-median problems in metric distance space, their research works in general distance space have rarely been found for many years. Consequently, in the thesis we study their computational complexities and design and analyze approximation algorithms for them. Our results are as follows.(1) Based on the practical observation, we first propose a class of UFL problem in general distance space, abbreviation for general UFL problem, in which the maximum connection cost is at mostωtimes the minimum connection cost, denoted by d_max/d_min≤ω. According to the hypothesis of NP (?) DTIME(n^O(loglogn)), by reducing set cover problem to general UFL problem and using the inapproximation result of the former, we prove that there are no polynomial-time algorithms for general UFL problem in which d_max/d_min≤ω+εwith approximation factors smaller than 1.243+0.3161n(ω-1), and that there are also no arbitrary constant factor approximation algorithms for general UFL problem. Let r_f and r_c be the ratios of the total facility cost and the total connection cost in approximated solution to corresponding parts in optimal solution. We also prove that there are no polynomial-time approximation algorithms for general UFL problem satisfying r_c<1+ (ω-1)e^-r_f, unless NP (?) DTIME(n^O(loglogn)).Since the 1.463 inapproximation result of UFL problem in metric distance space (short for metric UFL problem) was proposed by Guha et al. all the while one wishes to see the theoretical analysis of computational complexity concerning UFL problem in general distance space, and yet there are no related results in recent years all the time. Based on a special class of UFL problem, through strict analysis, we propose its inapproximation result for the first time. (2) We design a local search algorithm for general UFL problem in which d_max/d_min≤ω, and prove that the solution found by the algorithm satisfies L_f+2L_c≤O_f+ (1+ω)·O_c, where L_f, L_c, O_f, O_c are the total facility cost and the total connection cost in local optimum and global optimum, respectively. And then, it follows that the algorithm has an approximation factor of (1+ω)/α, 1≤α≤2. Next, we study the computational effect of the algorithm through experiment. The statistical results show that the average approximation ratio of all instances involved in the experiment is smaller than 1.001. By analyzing further the experimental data, we propose the improved strategy for the algorithm as well.UFL problem in general distance space was first studied by Hochbaum in 1982, who designed a polynomial-time algorithm for it with an O(logm) average approximation ratio, where m is the size of the input set of facilities. Then Hajiaghayi et al. in 2003 proved that it is still NP-hard and gave a polynomial-time algorithm with an approximation factor of 1nm. Since then the results of approximation algorithms for general UFL problem have not been found all the time. Compared with the existing algorithms for UFL problem in general distance space, the approximation ratio at worst of our algorithm will not be influenced by the size of instance.(3) Based on the model of the given general UFL problem, we propose and analyze a class of it-median problem in general distance space, abbreviation for general k-median problem. According to the hypothesis of NP (?) DTIME(n^O(loglogn)), by reducing set cover problem to general k-median problem, we prove that there are no polynomial-time algorithms for general k-median problem in which d_max/d_min≤ω+ε+E with approximation factors smallerthan 1+(ω-1)/e, and that there are also no arbitrary constant factor approximationalgorithms for general k-median problem. Further, we prove that if there is an polynomial-time algorithm with an approximation factor smaller than 1+2/e for k-median problem in metric distance space, short for metric k-median problem, then NP (?) DTIME(n^O(loglogn)). In 1992 Lin and Vitter ever conjectured that solving k-median problem with arbitrary connection costs is as difficult as set cover problem, and provided evidence that the inapproximated result of metric k-median problem is best possible via a reduction from set cover problem, and yet he did not give any strict proof for his conjecture. In 1999, Guha and Khuller revealed the computational complexity of metric UFL problem by giving the 1.463 inapproximability proof, while the inapproximated result of metric it-median problem has not been found all the time. Our related analysis of computational complexity of k-median problem fills in the research gap, and verifies the correctness of conjecture of Lin and Vitter .(4) A new local search algorithm for general k-median problem is proposed with running time of O(n). We prove that the approximation ratio of the algorithmis within 1+(ω-1)/2=(1+ω)/2 as it solves instances of general k-median problem in which d_max/d_min≤≧ by using a simple exchange operation. The unexpected effect is the form of the 1+(ω-1)/2 approximation degree is similar to the 1+(ω-1)/einapproximation result. Further, for metric k-median problem satisfying d_max/d_min≤5, we show that the approximation factor of the local search algorithm is at most 3. Finally, simulation experiment is used to study the impact of different k andωon the quality of the solution found by our algorithm. By analyzing the experimental results, we also propose an improved method for our algorithm.In 1992 Lin and Vitter gave a polynomial-time approximation algorithm for k-median problem in general distance space for the first time. His algorithm selected (1 + 1/ε)(1nn+1)k facilities, forε>0, and guaranteed the value of solution no more than (1+ε) times that of optimal solution. Since then, there are no results for the general k-median problem. For metric k-median problem, the (3+ε)-approximation algorithm proposed by Arya et al. is still the best result, and yet his analysis is not fit for general version of k-median problem. Solving metric k-median problem satisfying d_max/d_min≤5, our algorithm guarantees the approximation degree of the result is within 3, which is better than the result of 3+εin the literature[41].Two results above show that metric k-median subproblem in which d_max/d_min≤5 is also unable to be solved by any polynomial-time algorithm with an approximation factor smaller than 1+2/e, however, the approximation degree of solving it by using our algorithm within 3. In recent years, it is all along the main interests of the most of researchers that looking forα-approximation algorithm for metric k-median problem, whereα≤3, and yet they made virtually no progress all the time. We find a metric k-median subproblem for which there exists the approximation algorithm with approximation factor smaller than 3.(5) By using the idea of the algorithm for set cover problem, we design and implement a new greedy algorithm for k-median problem with running time of O(nmk), where n and m are the numbers of facilities and clients in the given problem, respectively. The computational effect of the algorithm is verified through the elaborate simulation experiment based on test sets of ORLIB , SLLIB , GRLIB and TSPLIB .To meet the need of QoS routing problem or similar applications, seeking fast and effective algorithms for k-median problem is always one of the most important research works. By using the algorithm of Jain and Vazirani for UFL problem, Jariyakul attempted to design an algorithm for k-median problem but found that the running time is too long and the computational effect is not good enough. Chrobak et al. also proposed a fast greedy algorithm for k-median problem. However, the O(n³m) running time of his algorithm is very high. The results of comparative experiment show that our algorithm outperforms the two algorithms above on the quality of solution and the running time.