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...
| প্রকাশিত: | Journal of the ACM 52, 4 (2005). |
|---|---|
| প্রধান লেখক: | |
| বিন্যাস: | প্রবন্ধ |
| ভাষা: | English |
| বিষয়গুলি: |