| Compact Location Problems with Budget and Communication Constraints (1998) | |||||||||||||||
Abstract | |||||||||||||||
| . We consider the problem of placing a specified number p of facilities on the nodes of a given network with two nonnegative edge-- weight functions so as to minimize the diameter of the placement with respect to the first weight function subject to a diameter-- or sum-- constraint with respect to the second weight function. Define an (ff; fi)--approximation algorithm as a polynomial--time algorithm that produces a solution within ff times the optimal value with respect to the first weight function, violating the constraint with respect to the second weight function by a factor of at most fi. We show that in general obtaining an (ff; fi)--approximation for any fixed ff; fi 1 is NP--hard for any of these problems. We also present efficient approximation algorithms for several of the problems studied, when both edge--weight functions obey the triangle inequality. 1 Introduction and Basic Definitions Several fundamental problems in location theory [HM79, MF90] involve finding a placem... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||