An O(log(*)n) approximation algorithm for the asymmetric p-center problem
VISHWANATHAN, S · DSpace (IIT Bombay) · 1996
The input to the asymmetricp-center problem consists of an integerpand ann×ndistance matrixDdefined on a vertex setVof sizen, wheredijgives the distance fromitoj. The distances are assumed to obey the triangle inequality. For a subsetS?Vthe radius ofSis the minimum distanceRsuch that every point inVis at a distance at mostRfrom some point inS. Thep-center problem consists of picking a setS?Vof sizepto minimize the radius. This problem is known to be NP-complete.For the symmetric case, whendij=dji, approximation algorithms that deliver a solution to within 2 of the optimal are known. David Shmoys, in his article 11, mentions that nothing was known about the asymmetric case. We present an algorithm that achieves a ratio ofO(log*n).