A platform for massive agent-based simulation and its evaluation
Gaku Yamamoto, Hideki Tai, et al.
AAMAS 2008
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 distance of any point from its center is as small as possible. We show that the ASYMMETRIC K-CENTER problem is hard to approximate up to a factor of log n O(1) unless NP ⊆ DTIME(n log logn). Since an O(log* n)-approximation algorithm is known for this problem, this resolves the asymptotic approximability of ASYMMETRIC k -CENTER. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. We also resolve the approximability threshold of the metric (symmetric) K-Center problem with costs. © 2005 ACM.
Gaku Yamamoto, Hideki Tai, et al.
AAMAS 2008
Shai Fine, Yishay Mansour
Machine Learning
Vijay K. Naik, Sanjeev K. Setia, et al.
Journal of Parallel and Distributed Computing
Bing Zhang, Mikio Takeuchi, et al.
NAACL 2025