A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem
share
In the d-dimensional cow-path problem, a cow living in ℝ^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 ℝ^d until it intersects ℋ. If the cow travels a total distance s to locate a hyperplane H whose distance from the origin was r ≥ 1, then the cow is said to achieve competitive ratio s / r. It is a classic result that, in ℝ^2, the optimal (deterministic) competitive ratio is 9. In ℝ^3, the optimal competitive ratio is known to be at most ≈ 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 √(d). In this note, we achieve a stronger lower bound of Ω̃(d^3/2).
READ FULL TEXT