cs.DScs.LG
On the Cyclic Assumption of the Cow-Path Search Algorithm
📅
👥 2 authors
arXiv:2610.10253v1
Authors
Yuan MaYiqun Lisa Yin
Abstract
In the cow-path problem, a cow must find a goal lying at an unknown distance on one of $w$ paths connected only at the origin, and performance is measured by competitive ratio. Kao, Reif and Tate designed an efficient randomized algorithm in which the cow visits the paths in a fixed cyclic order. They proved the algorithm is optimal for $w=2$, and subsequently Kao, Ma, Sipser and Yin proved its optimality for all $w$, with a claim that no algorithm does better than the best cyclic one. This note provides a detailed proof of that claim.
Paper Information
- arXiv ID:
- 2610.10253v1
- Published:
Related Categories
cs.DScs.LG