Journal article
Asymmetry in k-Center Variants
This paper explores three concepts: the k-center problem, some of its variants, and asymmetry. The k-center problem is fundamental in location theory. Variants of k-center may more accurately model real-life problems than the original formulation. Asymmetry is a significant impediment to approximation in many graph problems, such as k-center, facility location, k-median, and the TSP.We give an O(log*n)-approximation algorithm for the asymmetric weighted k-center problem.
Here, the vertices have weights and we are given a total budget for opening centers. In the p-neighbor variant each vertex must have p (unweighted) centers nearby: we give an O(log*k)-bicriteria algorithm using 2k centers, for small p.Finally, we show the following three versions of the asymmetric k-center problem to be inapproximable: priority k-center, k-supplier, and outliers with forbidden centers.
Language: | English |
---|---|
Year: | 2006 |
Pages: | 188-199 |
ISSN: | 18792294 and 03043975 |
Types: | Journal article |
DOI: | 10.1016/j.tcs.2006.05.009 |
ORCIDs: | Gørtz, Inge Li |