Backbone of the p-Median Problem
PMP is a well-known NP-hard problem with extensively wide applications in location science and clustering. In this paper, we presented computational complexity results about the backbone, the shared common parts of all the optimal solutions to the PMP. We
- PDF / 176,612 Bytes
- 6 Pages / 430 x 660 pts Page_size
- 45 Downloads / 222 Views
Abstract. PMP is a well-known NP-hard problem with extensively wide applications in location science and clustering. In this paper, we presented computational complexity results about the backbone, the shared common parts of all the optimal solutions to the PMP. We showed that it is intractable to approximate the backbone of the PMP with any performance guarantee under the assumption that P ≠ NP . Keywords: p-median, computational complexity, backbone.
1 Introduction Given a set of users and potential facilities, the p-median problem (PMP) is to identify the locations of a pre-determined number of facilities, in such a way as to minimize the total distance that user must traverse to reach its nearest facility. The PMP is a wellknown NP-hard problem (Kariv and Hakimi, 1979), with wide applications in location science and clustering. Since it is intractable for NP-hard problems to obtain optimal solutions, many heuristics have been developed for solving large PMP instances. A recent survey on the state of the art in this area can be found in Mladenović et al. (2007). As an important tool to design heuristics for NP-hard problems, the backbone (i.e., the shared common parts of all optimal solutions for a NP-hard problem instance) has received widespread attention because no optimal solution can be computed unless the backbone is obtained. However, backbone analysis is still at the beginning state with few theoretical analysis results. As to our knowledge, the only analytical result is given by Kilby, Slaney, and Walsh (2005) that it is NP-hard to obtain the backbone of the TSP. Its basic idea is to map any instance of the TSP to an instance whose solution is unique. Therefore, finding the backbone of the modified instance is equivalent to finding an optimal solution of the original instance. This paper investigates the computational complexity of the backbone of the PMP as follows. Firstly, we proved that there is no polynomial time algorithm to obtain the full backbone of the PMP under the assumption that P ≠ NP . The same principle by Kilby, Slaney, and Walsh (2005) was used in the proof. We gave the definition of the compact PMP instance and showed that its backbone is the same to the backbone of the related PMP instance. By constructing the biased compact PMP instance with unique optimal solution, we proved it is intractable to approximate the backbone assuming that P ≠ NP . Secondly, we indicated that it is intractable to obtain a fixed fraction of the backbone under the assumption that P ≠ NP as well. M.A. Orgun and J. Thornton (Eds.): AI 2007, LNAI 4830, pp. 699–704, 2007. © Springer-Verlag Berlin Heidelberg 2007
700
H. Jiang, X. Zhang, and M. Li
2 Preliminaries In this section, we shall give some related definitions and related properties. Definition 1. Given a set F = {1, 2,..., m} of m potential facilities, and a set U = {1, 2,..., n} of n users, a matrix D = (dij )n× m where dij represents the distance the user ui away from the facility f j for all i ∈ U and j ∈ F , a predefined p < m , the PMP instanc
Data Loading...
