On the approximation of the minimum disturbance \(p\)-facility location problem (Q1348254)

The paper deals with a \(p\)-median discrete location problem where \(n\) costumers receive different potential disturbances from \(m\) facilities (aerials, garbage dumps, nuclear power plants). The amount of disturbance is given by an \(n \times m\) non-negative integer matrix \(D\). The problem is to select at least \(p\) out of the \(m\) facilities to be opened such that the maximum disturbance, over the \(n\) costumers, is minimized. The author argues briefly why the problem is NP-hard and that it does not belong to the class PTAS of problems admitting a polynomial time approximation scheme. In the paper it is shown, however, that the minimum disturbance \(p\)-facility location problem can be deterministically approximated within \(O(\rho (\log n + \log p))\), where \(\rho\) is the ratio between the biggest and the smallest positive entry of \(D\). In order to derive this result, first a randomized algorithm is developed. This algorithm is then derandomized by the method of conditional probabilities.