Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This note provides a rigorous proof for the optimality of the cyclic cow-path search algorithm for all $w$ paths, resolving a long-standing conjecture. The cyclic strategy, which visits paths in a fixed order, achieves the best possible competitive ratio against an adversary. This work solidifies the theoretical understanding of optimal search strategies in this fundamental problem.
The optimal strategy for the cow-path problem is provably cyclic, meaning no search algorithm can outperform a fixed path traversal order.
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.