A lower bound for metric 1-median selection
详细信息 查看全文
- 作者：Ching-Lueh Chang1 ; clchang@saturn.yzu.edu.tw" class="auth_mail" title="E-mail the corresponding author
- 关键词：1-Median selection ; Metric space ; Sublinear-time algorithm ; Sublinear-query algorithm ; Query complexity
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：44-51
- 全文大小：388 K
文摘
- •
Given oracle access to an n-point metric space, let metric 1-median be the problem of finding a point with the minimum average distance to the other points.
- •
We show that metric 1-median has no deterministic o(n2)-query (4−ϵ)-approximation algorithms for any constant ϵ>0.