AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem

✍ Scribed by Rina Panigrahy; Sundar Vishwanathan

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 130 KB
• Volume: 27
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0921

✦ Synopsis

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 gives the i j distance from i to j. The distances are assumed to obey the triangle inequality. For a subset S : 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 : V of size p to minimize the radius. This problem is known to be NP-complete.

For the symmetric case, when d s d , approximation algorithms that deliver a i j ji w x 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 Ž U . algorithm that achieves a ratio of O log n .