pipette
ENEnglish

On the Cyclic Assumption of the Cow-Path Search Algorithm

Yuan Ma, Yiqun Lisa Yin

Preprint

En palabras de los autores

In the cow-path problem, a cow must find a goal lying at an unknown distance on one of 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 , and subsequently Kao, Ma, Sipser and Yin proved its optimality for all , with a claim that no algorithm does better than the best cyclic one. This note provides a detailed proof of that claim.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.