This talk presents work by Sundar Vishwanathan. Imagine you
are going to build $p$ service centers and wish to know the
best set of locations for them. Examples where this problem
arises include fire stations, and ambulance
centers. The $p$-center problem is to place the service
centers so that no vertex is too far away from its nearest
center, i.e., to minimize the maximum distance to the nearest
center.
This problem is known to be NP-complete. When distances are
symmetric ($d_{ij}=d_{ji}$), we can achieve a 2-approximation
algorithm. For the asymmetric case, no constant-factor
approximation algorithm is known. In this talk, we present
an algorithm for the asymmetric problem which achieves an
$O(\log^* n)$ approximation factor.