Record Details


Field	Value

Title	An O(log*n) approximation algorithm for the asymmetric p-center problem

Names	PANIGRAHY, R (author) VISHWANATHAN, S (author)
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	0196-6774
Related Item
Related Item

ICAR Research Data Repository for Knowledge Management