On the Cyclic Assumption of the Cow-Path Search Algorithm

Yuan Ma; Yiqun Lisa Yin

cs.DSOct 7, 2026

On the Cyclic Assumption of the Cow-Path Search Algorithm

Authors: Yuan Ma, Yiqun Lisa Yin

Organizations: MIT

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.

Figures & tables

Panel of Figure 1 — Figure 1: Comparison of $X$ and $X^{*}$ in the proof of Proposition 1.

Panel of Figure 2 — Figure 2: Comparison of $X$ and $X^{*}$ in Lemma 2. After relabelling, the frontiers of $X^{*}$ match those of $X$ , allowing the same continuation of the algorithm.

Explore similar work

Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem
Apr 17, 2026Srikar Gouru, Ariel Felner, Jiaoyang LiMulti-Robot Motion Planning Multi-Agent Path Finding
Carnegie Mellon University · Ben-Gurion University of the Negev
COMPASS: Ordered Clustered Routing at 100K Scale
Sep 17, 2026Ido Greenberg, Hugo Linsenmaier, Piotr Sielski +4Traveling Salesperson Problem Combinatorial Optimization
NVIDIA
Counterfactual Routing Using Integer Programming with Constraint Generation
Sep 3, 2026Daniël Vos, Sterre LutzCounterfactual Explanations Combinatorial Optimization
Delft University of Technology

Apr 17, 2026, cs.MAJ/K move · Enter open · S save

Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem

Srikar Gouru, Ariel Felner, Jiaoyang Li

Carnegie Mellon University · Ben-Gurion University of the Negev

Multi-Robot Motion Planning Multi-Agent Path Finding

Open paper AskPDF arXiv

In this paper, we tackle the Multiple Watchman Route Problem (MWRP), which aims to find a set of paths that M watchmen can follow such that every location on the map can be seen by at least one watchman. First, we propose multiple methods to reduce the state space over which a search needs to be conducted by pruning map areas that are guaranteed to be seen en route to other areas. Next, we introduce MWRP-CP3, an efficient optimal planner that combines these methods with techniques that improve the quality and calculation time of existing heuristics. We present several suboptimal algorithms with bounds on solution quality, including MxWA*, a general variant of weighted A* for makespan problems. We also present anytime variations of our suboptimal algorithms, as well as techniques to improve an existing suboptimal solution by solving multiple decomposed sub-problems. We show that MWRP-CP3 can reduce the search space by more than 95% and runs more than 200x faster than existing optimal algorithms on 2D grid maps. We also show that our suboptimal algorithms solve maps 3x larger than those solvable by MWRP-CP3. See mwrp-cp3.github.io for the open source codebase and video demonstrations.

Abstract

Explore similar work

Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem

COMPASS: Ordered Clustered Routing at 100K Scale

Counterfactual Routing Using Integer Programming with Constraint Generation