Proof confirms cyclic search method is best for multipath search

On the Cyclic Assumption of the Cow-Path Search Algorithm

Data Structures and AlgorithmsMachine Learning

Summary

The paper studies a problem where a searcher must find a target hidden on one of several paths starting from the same point, without knowing the target’s distance. Earlier work designed a randomized search method that checks the paths in a fixed order cyclically and showed it’s optimal when there are two paths. The authors clarify and prove that this cyclic approach is actually the best possible for any number of paths, meaning no other algorithm can outperform it. This settles a previous claim about the optimality of the cyclic search pattern.

What this means in practice

  • For robot navigation teams: Use the proven optimal cyclic search strategy for robots tasked with finding objects located along multiple paths from a fixed start point.
  • For network fault diagnosis teams: Apply the cyclic search method to systematically identify faults occurring on one of several network routes originating from a central hub.

A theory result. No direct application yet.

Authors

Yuan Ma, Yiqun 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.