Faster Symmetric Rendezvous on Four or More Locations
This solves an open problem in theoretical computer science regarding rendezvous algorithms, providing a concrete improvement for multi-location scenarios.
The paper tackled the symmetric rendezvous problem for n≥4 locations by constructing a new strategy that reduces the expected meeting time compared to the previously known Anderson-Weber strategy, which was suboptimal for these cases.
In the symmetric rendezvous problem two players follow the same (randomized) strategy to visit one of $n$ locations in each time step $t=0,1,2,\dots$. Their goal is to minimize the expected time until they visit the same location and thus meet. Anderson and Weber [J. Appl. Prob., 1990] proposed a strategy that operates in rounds of $n-1$ steps: a player either remains in one location for $n-1$ steps or visits the other $n-1$ locations in random order; the choice between these two options is made with a probability that depends only on $n$. The strategy is known to be optimal for $n=2$ and $n=3$, and there is convincing evidence that it is not optimal for $n=4$. We show that it is not optimal for any $n\geq 4$, by constructing a strategy with a smaller expected meeting time.