| Compact Location Problems (1998) | |||||||||||||||
Abstract | |||||||||||||||
| We consider the problem of placing a specified number (p) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a number of problems arising in facility location, statistical clustering, pattern recognition, and also processor allocation problems in multiprocessor systems. We consider the problem under three different objectives, namely minimizing the diameter, minimizing the average distance, and minimizing the variance. We observe that in general, the problem is NP-hard under any of the objectives. Further, even obtaining a constant factor approximation for any of the objectives is NP-hard. We present a general framework for obtaining near-optimal solutions to the compact location problems for the above measures, when the distances satisfy the triangle inequality. We show that this framework can be extended to the case when there are also node weights We also investigate the complexity and approximabil... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||