AN O(LOG-ASTERISK-N) APPROXIMATION ALGORITHM FOR THE ASYMMETRIC P-CENTER PROBLEM

The input to the asymmetric p-center problem consists of an integer p and an n x n distance matrix D defined on a vertex set V of size n, wh ere d(ij) gives the distance from i to j. The distances are assumed to obey the triangle inequality. For a subset S subset of or equal to V the radius of S is the minimum distance R such that every point in V i s at a distance at most R from some point in S. The p-center problem c onsists of picking a set S subset of or equal to V of size p to minimi ze the radius. This problem is known to be NP-complete. For the symmet ric case, when d(ij) = d(ji), approximation algorithms that deliver a solution to within 2 of the optimal are known. David Shmoys, in his ar ticle [11], mentions that nothing was known about the asymmetric case. We present an algorithm that achieves a ratio of O(logn). (C) 1998 A cademic Press.