ICAR Research Data Repository for Knowledge Management
DSpace at IIT Bombay
View Archive InfoMetadata
| Field | Value |
| Title | An O(log*n) approximation algorithm for the asymmetric p-center problem |
| Names |
PANIGRAHY, R
VISHWANATHAN, S |
| Date Issued | 1998 (iso8601) |
| Abstract | 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, where 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 is at a distance at most R from some point in S. The p-center problem consists of picking a set S subset of or equal to 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). (C) 1998 Academic Press. |
| Genre | Article; Proceedings Paper |
| Identifier | JOURNAL OF ALGORITHMS,27(2)259-268 |