Papers for

network fault diagnosis teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Proof confirms cyclic search method is best for multipath search

On the Cyclic Assumption of the Cow-Path Search Algorithm

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.

Wed 7 OctData Structures and AlgorithmsMachine Learning
The gist
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.
Open → 2610.10253v1