Lune

SODA2022Top-tier venue

Competitive Strategies for Symmetric Rendezvous on the Line

Max Klimm, Guillaume Sagnol, Martin Skutella, Khai Van Tran

Abstract

In the Symmetric Rendezvous Search on the Line with Unknown Initial Distance, two identical agents are placed on the real line with their distance, the other's location, and their orientation unknown to them. Moving along the line at unit speed and executing the same randomized search strategy, the agents' goal is to meet up as early as possible. The expected meeting time obviously depends on the unknown initial distance and orientations. The quality of a randomized search strategy is thus measured by its competitive ratio, that is, the ratio of the expected meeting time and the earliest possible meeting time (half the initial distance). We present a class of successively refined randomized search strategies together with a rigorous mathematical analysis of their continuously improved competitive ratios. These strategies all rely on the basic idea of performing an infinite sequence of steps of geometrically increasing size in random directions, always returning to the agent's initial position before starting the next step. In addition, our more refined strategies use two novel ideas. First, remembering their past random choices, the agents randomly choose the direction of the next step in a Markov-chain-like manner. Second, choosing the next few random directions in advance, each agent may combine consecutive steps in the same direction into one longer step. As our main result, we show that this combination of looking into the past as well as into the future leads to a substantially improved competitive ratio of 13.93 compared to the previously best known bound of 24.85 (Ozsoyeller et al. 2013).

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Weighted k-Server Admits an Exponentially Competitive AlgorithmAdithya Bijoy, Ankit Mondal, Ashish ChiplunkarSODA 2026
  2. Online Search with Maximum ClearanceSpyros Angelopoulos, Malachi VossAAAI 2021 · 2 citations
  3. The Randomized k-Server Conjecture Is False!Sébastien Bubeck, Christian Coester, Yuval RabaniSTOC 2023 · 6 citations
  4. Breaking the k/ log k Barrier in Collective Tree Exploration via Tree-MiningRomain CossonSODA 2024 · 1 citation
  5. Shortest Paths without a Map, but with an Entropic RegularizerSébastien Bubeck, Christian Coester, Yuval RabaniFOCS 2022 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines