Finite Dominating Set for the p-Facility Cent-Dian Network Location Problem

A dominating set for a location problem is a set of points that contains an opti-mal solution for all instances of the problem. The p-facility location problems on a network appear when the possible selections for locating the facilities are the sets of p points of the network. Hooker, Garfinkel and Chen [4] consider a theoretical result to extend the dominating set for the 1-facility problems to the corresponding p-facility problems, and apply this result to propose a finite dominating set for the p-facility cent-dian problem on a network. The optimal solutions of the cent-dian problems are those minimizing a linear combination of the center and median ob-jective functions. Since it is known that the set of vertices and local centers is a dominating set for the single facility cent-dian problem, they claim that it is also a dominating set for the p-facility cent-dian problem. We show a counterexample for p = 2 and give an alternative finite dominating set for the p-facility cent-dian. We also provide a solution method that avoids the exhaustive search in all the sets of p points of this dominating set