论文标题
$ d $ dimensional的牛path问题几乎紧密的下限
A Nearly Tight Lower Bound for the $d$-Dimensional Cow-Path Problem
论文作者
论文摘要
在$ d $维牛pat的问题中，生活在$ \ mathbb {r}^d $中的牛必须找到$（d-1）$ - 尺寸尺寸超平面$ h $，其位置未知。牛可以找到$ h $的唯一方法是漫游$ \ mathbb {r}^d $，直到它相交$ \ mathcal {h} $。如果牛在总距离上$ s $来定位与原始距离为$ r \ ge 1 $的超平面$ h $，则据说牛可以达到竞争比率$ s / r $ $。 这是一个经典的结果，在$ \ mathbb {r}^2 $中，最佳（确定性）竞争比为$ 9 $。在$ \ mathbb {r}^3 $中，最佳竞争比率最多为$ \ \ 13.811 $。但是在较高的维度中，$ d $与最佳竞争比率之间的渐近关系仍然是一个悬而未决的问题。由于Antoniadis等人而引起的最佳上限和下限是$ O（d^{3/2}）$和$ω（d）$，留出的间隙约为$ \ sqrt {d} $。在本说明中，我们获得了$ \tildeΩ（d^{3/2}）$的更强下限。
In the $d$-dimensional cow-path problem, a cow living in $\mathbb{R}^d$ must locate a $(d - 1)$-dimensional hyperplane $H$ whose location is unknown. The only way that the cow can find $H$ is to roam $\mathbb{R}^d$ until it intersects $\mathcal{H}$. If the cow travels a total distance $s$ to locate a hyperplane $H$ whose distance from the origin was $r \ge 1$, then the cow is said to achieve competitive ratio $s / r$. It is a classic result that, in $\mathbb{R}^2$, the optimal (deterministic) competitive ratio is $9$. In $\mathbb{R}^3$, the optimal competitive ratio is known to be at most $\approx 13.811$. But in higher dimensions, the asymptotic relationship between $d$ and the optimal competitive ratio remains an open question. The best upper and lower bounds, due to Antoniadis et al., are $O(d^{3/2})$ and $Ω(d)$, leaving a gap of roughly $\sqrt{d}$. In this note, we achieve a stronger lower bound of $\tildeΩ(d^{3/2})$.
