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

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...

Cijeli opis

Bibliografski detalji
Izdano u:Journal of the ACM 52, 4 (2005).
Glavni autor: Chuzhoy, Julia
Format: Članak
Jezik:English
Teme:
Theory of computation.
Analysis of algorithms and problem complexity.
Nonnumerical algorithms and problems.
Mathematics of computing.
Discrete mathematics.
Combinatorics.
Algorithms.
Theory.