论文标题
确定性度量$ 1 $ -Median选择，很少查询
Deterministic metric $1$-median selection with very few queries
论文作者
论文摘要
给定一个$ n $ - 点公制空间$（m，d）$，{\ sc metric $ 1 $ -Median}要求在m $最小化$ \ sum_ {x \ in m} \ in m} \，d（p，x）$中提供点$ p \。我们表明，对于每个可计算函数，$ f \ colon \ mathbb {z}^+\ to \ mathbb {z}^+$满足$ f（n）=ω（n）=ω（1）$，{\ sc metric $ 1 $ -Median}具有确定性的，$ O（n）$ - QUERY，$ - QUERY，$ o（n）$ o（n）$ o（n） 算法。以前，没有确定性的$ o（n）$ - 查询$ o（n）$ - 近似算法以{\ sc metric $ 1 $ -Median}而闻名。在负面方面，我们证明{\ sc metric $ 1 $ -Median}的每个确定性$ o（n）$ - 查询算法都不是$（δ\ log n）$ - 对于足够小的常数$δ> 0 $而言。我们还驳斥了确定性$ o（n）$ - 查询$ o（\ log n）$ - 近似算法的存在。
Given an $n$-point metric space $(M,d)$, {\sc metric $1$-median} asks for a point $p\in M$ minimizing $\sum_{x\in M}\,d(p,x)$. We show that for each computable function $f\colon \mathbb{Z}^+\to\mathbb{Z}^+$ satisfying $f(n)=ω(1)$, {\sc metric $1$-median} has a deterministic, $o(n)$-query, $o(f(n)\cdot\log n)$-approximation and nonadaptive algorithm. Previously, no deterministic $o(n)$-query $o(n)$-approximation algorithms are known for {\sc metric $1$-median}. On the negative side, we prove each deterministic $O(n)$-query algorithm for {\sc metric $1$-median} to be not $(δ\log n)$-approximate for a sufficiently small constant $δ>0$. We also refute the existence of deterministic $o(n)$-query $O(\log n)$-approximation algorithms.
