Randomization Helps in Online Graph Exploration: Breaking the Deterministic Lower Bound on Cycles

Abstract

In online graph exploration, introduced by Kalyanasundaram and Pruhs (1994), an agent must visit all vertices of an initially unknown weighted graph and return to its starting position, while the graph is revealed only locally at visited vertices. Although the problem has attracted considerable attention, previous work has focused exclusively on deterministic algorithms. Randomized strategies are often substantially harder to analyze because of a fundamental challenge inherent to exploration. In this work, we give the first positive result showing that randomization can improve competitive guarantees in online graph exploration. To this end, we focus on cycles, a simple graph class which nevertheless captures a key difficulty of online exploration. Our main contribution is \(\textsc{RandHeavyTest}\), a randomized algorithm for online exploration of cycles whose competitive ratio we prove to be at most 1.315. This establishes a strict separation from the deterministic setting, where the optimal competitive ratio is $\approx 1.366$, and thus gives the first provable advantage of randomization in online graph exploration. A key step towards this result is a new, simplified optimal deterministic algorithm, \(\textsc{HeavyTest}\), whose formulation naturally suggests the randomized variant. We complement our upper bounds with lower bounds of 1.115 for arbitrary randomized algorithms and 1.207 for the natural class of so-called forward-greedy algorithms, which includes \(\textsc{RandHeavyTest}\).

17 pages, 3 figures

Topics & keywords