|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
Imagine you have a delivery service. You want to place your k delivery hubs at locations that minimize the maximum distance between customers and their nearest hubs. This is the k-center problem---a type of clustering problem that is similar to the facility location and k-median problems. The motivation for the asymmetric k-center problem, in our example, is that traffic patterns or one-way streets might cause the travel time from one point to another to differ depending on the direction of travel. Variants of k-center may more accurately model real-life problems than the original formulation. 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. Host: Jørgen Bang-Jensen SDU HOME | IMADA HOME | Previous Page Last modified: February 8, 2005. Joan Boyar (joan@imada.sdu.dk) |