A Jeep Crossing a Desert of Unknown Width (Extended Abstract)

SOCS-22 Volume 15

Volume

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search

Extended Abstracts

The classic jeep problem concerns crossing a desert wider than the range of the jeep, by preplacing caches of fuel. The optimal strategy for a given distance is known, but we consider the case where we don't know the distance in advance. We evaluate strategies by their competitive ratio, which is the worst-case ratio of the cost of the strategy, divided by the cost of an optimal solution had we known the distance in advance. We show that no strategy with a fixed sequence of caches can achieve a finite competitive ratio. The optimal strategy is an iterative one that uses the optimal known-distance strategy to reach a sequence of target distances, emptying all caches between iterations. An optimal iterative strategy doubles the cost of each successive iteration, and achieves a competitive ratio of four. This paper has been published in the American Mathematical Monthly.

10.1609/socs.v15i1.21791