The input to the asymmetric p-center problem consists of an integer p and an n * n distance matrix D defined on a vertex set V of size n, where d_(ij) gives the distance from i to j. The distances are assumed to obey the triangle inequality. For a subset S is contained in V the radius of S is the minimum distance R such that every point in V is at a distance at most R from some point in S. The p-center problem consists of picking a set S is contained in V of size p to minimize the radius. This problem is known to be NP-complete. For the symmetric case, when d_(ij) = d_(ji), 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 of O(log~* n).
展开▼
机译：非对称p中心问题的输入由整数p和在大小为n的顶点集V上定义的n * n距离矩阵D组成，其中d_（ij）给出从i到j的距离。假定距离服从三角形不等式。对于包含在V中的子集S，S的半径是最小距离R，以使V中的每个点与S中的某个点之间的距离最大为R。p中心问题包括选择一个S集。大小为p的V以最小化半径。已知此问题是NP完全的。对于对称情况，当d_（ij）= d_（ji）时，已知将解法解到最佳值2之内的近似算法。 David Shmoys在他的文章[11]中提到，关于不对称情况一无所知。我们提出了一种实现O（log〜* n）比的算法。
展开▼
