A lower bound for metric 1-median selection

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：1-Median selection,Metric space,Sublinear-time algorithm,Sublinear-query algorithm,Query complexity

论文评审过程：Received 3 May 2014, Revised 15 August 2016, Accepted 21 August 2016, Available online 9 September 2016, Version of Record 14 November 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.08.004