tailieunhanh - A note on the p−center problem

The p-center problem is to locate p facilities in a network so as to minimize the longest distance between a demand point and its nearest facility. In this paper, we give a construction on a graph G which produces an infinite ascending chain G=G0≤G1≤ G2 ≤ . of graphs containing G such that given any optimal solution X for the p-center problem on G , X is an optimal solution for the p-center problem on Gi for any i ≥ 1. | Yugoslav Journal of Operations Research 21 (2011), Number 2, 199-204 DOI: A NOTE ON THE P − CENTER PROBLEM Nader JAFARI RAD Department of Mathematics, Shahrood University of Technology, Shahrood, Iran Received: February 2010 / Accepted: November 2011 Abstract: The p - center problem is to locate p facilities in a network so as to minimize the longest distance between a demand point and its nearest facility. In this paper, we give a construction on a graph G which produces an infinite ascending chain G = G0 ≤ G1 ≤ G2 ≤ . of graphs containing G such that given any optimal solution X for the p - center problem on G , X is an optimal solution for the p - center problem on Gi for any i ≥ 1 . Keywords: Location theory, p - center problem. MSC: 90B80, 05CXX. 1. INTRODUCTION Network location problems are concerned with finding the right locations to place one or more facilities in a network of demand points, ., customers represented by nodes in the network, that optimize a certain objective function related to the distance between the facilities and the demand points. Usually, the facilities to be located are desirable, ., customers prefer to have the facilities located as close to them as possible. For example, services such as police and fire stations, hospitals, schools, and shopping centers are typical desirable facilities. The p-center problem is to locate p facilities in a network so as to minimize the longest distance between a set of n demand points and the p facilities. This problem is central to the field of location theory and logistics, and has been subject to extensive research. For references in p-center problem see for example [1-11]. 200 N. J. Rad / A Note On The P − center Problem We model the network as a graph G = (V , E ) , where V = {v 1 ,v 2 ,.,v n } is the vertex set with V = n and E is the edge set with E = m . We assume that the demand points coincide with the vertices, and .