A lower bound for metric 1-median selection

作者：Chang Ching Lueh^*

来源：Journal of Computer and System Sciences, 2017, 84: 44-51.

DOI：10.1016/j.jcss.2016.08.004

• 1-Median selection
• Metric space
• Sublinear-time algorithm
• Sublinear-query algorithm
• Query complexity

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(n(2))-query (4-is an element of)-approximation algorithms for any constant is an element of > 0.

• 出版日期2017-3