Asymmetric k-center is log* n-hard to approximate.

In the ASYMMETRIC k-CENTER problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum...

Mô tả đầy đủ

Chi tiết về thư mục

Xuất bản năm:	Journal of the ACM 52, 4 (2005).
Tác giả chính:	Chuzhoy, Julia
Định dạng:	Bài viết
Ngôn ngữ:	English
Những chủ đề:	Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Mathematics of computing. Discrete mathematics. Combinatorics. Algorithms. Theory.