Asymmetry in k-center variants

Abstract

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 weightedk -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 2 k ce..