| Complexity and Approximability of Certain Bicriteria Location Problems (1998) | |||||||||||||||
Abstract | |||||||||||||||
| . We investigate the complexity and approximability of some location problems when two distance values are specified for each pair of potential sites. These problems involve the selection of a specified number of facilities (i.e. a placement of a specified size) to minimize a function of one distance metric subject to a budget constraint on the other distance metric. Such problems arise in several application areas including statistical clustering, pattern recognition and load--balancing in distributed systems. We show that, in general, obtaining placements that are near-optimal with respect to the first distance metric is NP -- hard even when we allow the budget constraint on the second distance metric to be violated by a constant factor. However, when both the distance metrics satisfy the triangle inequality, we present approximation algorithms that produce placements which are near-optimal with respect to the first distance metric while violating the budget constraint only by a smal... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||