Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951254 | Journal of Computer and System Sciences | 2017 | 8 Pages |
Abstract
Consider the problem of finding a point in an n-point metric space with the minimum average distance to all points. We show that this problem has no deterministic o(n2)-query (4âϵ)-approximation algorithms for any constant ϵ>0.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ching-Lueh Chang,