CS Paper Radar

Oblivious Self-Distance Symmetric Rendezvous on the Integer Line

Konstantinos Georgiou, Claude Gravel, Joey Kapusin, Lazar Mandic

cs.DM ·submitted 2026-09-12 00:47 UTC · v2

Abstract

Symmetric rendezvous on the line is a search problem in which two agents, initially placed at distance $2d$, must follow the same randomized strategy to meet as quickly as possible. In the standard model, agents may condition their actions on the entire execution history, and both the known- and unknown-distance variants admit expected rendezvous time $Θ(d)$. We study the role of memory by introducing oblivious self-distance strategies, in which an agent's decision depends only on her position relative to her own starting location. For an initial separation of $2d$, let $R_d$ denote the optimal oblivious expected rendezvous time in the known-distance setting. We develop two finite-state frameworks based on absorbing Markov chains. Truncated chains give computable upper bounds through finite-support strategies, while weak-peek chains give lower bounds through a revealed-information relaxation. Together, they provide a mechanism for certifying optimality. Using that mechanism, we determine $R_1$ exactly and prove that it is attained by a finite-support strategy. For $d=2,\ldots,6$, numerical optimization gives the same truncation structure and objective values, yielding rigorous upper bounds below $7.83d^2$. We do not prove that the computed weak-peek minimizers are global, but the stability of the computations leads us to conjecture that they are, in which case the corresponding truncated strategies are optimal. We also prove that $R_d=Θ(d^2)$. In the unknown-distance setting, we construct a universal strategy, independent of $d$, with expected rendezvous time $O(d^{2+η})$ for every fixed $η>0$. Thus, under the memory restriction, the known-distance rendezvous time becomes quadratic, while near-quadratic performance remains possible even without knowing $d$. The asymptotic analysis uses birth-death Markov chains and their electrical-network interpretation.

Closest papers

Nearest neighbours by meaning across the whole index.

Rendezvous under Variable Disorientation:The Algorithmic Power of Fixed Unit Distance

cs.DC ·2026-10-07 ·Koichi Wada, Toshimitsu Masuzawa, Yuichi Sudo
theory similarity 0.64
Abstract

We study deterministic Rendezvous of two robots with lights under weak geometric and synchronization assumptions. Our focus is on Variable Disorientation (VD), where each robot may arbitrarily rotate, reflect, and rescale its local coordinate system at every \Look, and on VD+Fixed-Unit-Distance (FUD), where each robot's local unit distance remains fixed. We consider the one-sided visibility models FSTA and FCOM, and schedulers ranging from the energy-restricted RSYNCH and R-RSYNCH to fully asynchronous executions. Under VD, we prove color-independent impossibility results for FSTA under SSYNCH and for FCOM under ASYNCH, and establish sharp two-color boundaries under RSYNCH and R-RSYNCH. Under VD+FUD, we introduce periodic distance classes, which turn multipl icative changes of the physical distance into predictable cyclic phase shifts. This technique yields a two-color self-stabilizing non-$L$-Rendezvous algorithm for both FSTA and FCOM under RSYNCH and R-RSYNCH even with Non-Rigid movement. Under Rigid movement, periodic distance classes further yield an optimal three-color non-quasi-self-stabilizing algorithm for FSTA under SSYNCH, a four-color FSTA algorithm under $M$-atomic ASYNCH, and a four-color FCOM algorithm under CM-atomic ASYNCH. By guarding the latter phase mechanism with two additional colors and replacing its initial swap by passive initialization, we obtain a six-color FCOM algorithm under full ASYNCH, improving the previous twelve-color upper bound by a factor of two. These results show that a fixed local metric can serve as persistent cyclic memory, and clarify how metric stability, one-sided visibility, and scheduler atomicity jointly determine Rendezvous solvability and color complexity.

0.20

Mechanism Design for Facility Location Games Under a Prelocated Facility

cs.GT ·2026-08-31 ·Genjie Qin, Qizhi Fang, Wenjing Liu
publishedtheory similarity 0.63
Abstract

We study the problem of locating a new homogeneous facility under a prelocated facility. Here, a set of $n$ agents is located on a real line or a circle, each of whom has her location as private information, and her cost is the (expected) distance from her location to the nearest facility. Our goal is to design mechanisms which can approximately minimize the maximum cost or the social cost while eliciting agents' private information truthfully (i.e., strategy-proof). Based on real-life scenarios, we consider the problem in two settings: the general setting where each agent can be located at both sides of the prelocated facility, and the special setting where all the agents are located at the same side of the prelocated facility. For agents on a line, in the general setting, we design the best possible deterministic strategy-proof mechanism with $2$-approximation and provide a lower bound of $1.5-ε\textbf{ }(ε>0)$ for any randomized strategy-proof mechanism under the maximum cost objective. For the social cost, we obtain an upper bound of $n$ for deterministic strategy-proof mechanisms and lower bounds of $1.5$ and $1.0425$ for any deterministic strategy-proof mechanism and any randomized strategy-proof mechanism, respectively. In the special setting, we further provide a randomized strategy-proof $5/3$-approximation mechanism for the maximum cost and a deterministic strategy-proof $(n-1)$-approximation mechanism for the social cost. For agents on a circle, we provide a deterministic strategy-proof 2-approximation mechanism under the maximum cost objective.

0.39

Universal Rendezvous of Anonymous Agents with Footprints

cs.DC ·2026-08-10 ·Bibhuti Das
similarity 0.63
Abstract

Deterministic rendezvous for two anonymous mobile agents starting simultaneously from two distinct nodes of an anonymous connected graph and navigating synchronously in the graph requires that they meet at some node. An instance of the rendezvous problem is the underlying graph, together with two distinct nodes that are the initial positions of the agents. Such an instance is said to be feasible if there is a deterministic algorithm guaranteeing rendezvous, possibly valid only for this instance. A rendezvous algorithm is said to be universal for a class of instances if it guarantees rendezvous for all feasible instances from this class. We consider the model with footprints: whenever an agent visits an unmarked node, it leaves a permanent footprint on it, and all footprints are identical. This paper aims at answering the open problem from the paper by Das and Pelc (SPAA 2026), asking whether there exists a universal rendezvous algorithm for the class of all instances in the model with footprints. We propose a universal rendezvous algorithm for the class of all instances where the underlying graph is connected (finite or countably infinite) in the model with footprints. This shows the existence of a universal algorithm for the class of all instances in the model with footprints, which is an affirmative answer to the open problem.

0.04

Strategic Facility Location in Euclidean Spaces

cs.GT cs.DS ·2026-09-04 ·Kim Thang Nguyen, Lucas Perotin, Bertrand Simon
similarity 0.62
Abstract

The strategic facility location problem is defined as follows: $n$ agents report their location in a metric space, and the objective is to design a \emph{mechanism} deciding the (possibly randomized) location of a facility such that agents have no incentive to lie about their position. We focus on the egalitarian cost, which means that the goal of the mechanism is to minimize the expected maximal facility-agent distance. Meanwhile, mechanisms must be \emph{truthful} (or \emph{strategyproof}): no agent may decrease their expected distance to the facility via lying on their location. Designing truthful mechanisms minimizing the approximation ratio is a well-studied problem, and the optimal solution is known for the real line. We focus in this paper on higher dimension Euclidean spaces, for which gaps remain between the best known lower and upper bounds. We first show that, maybe counter-intuitively, the problem is easier for two agents on the plane rather than on the line: the mechanism can exploit the additional dimension to prevent more efficiently agent lies. Based on this intuition, we devise lower bounds for $\mathbb R^d$ asymptotically matching the best known approximation factor of $2$ for large $d$. We also provide novel mechanism ideas, improving over the best known algorithms on the plane, and when the agents belong to $\mathbb R^d$ but the facility may use an additional dimension.

0.03

Maximum-Cost Strategic Facility Location: The Limits of Randomization

cs.GT ·2026-08-17 ·Jabari Hastings, Misha Ivkov
similarity 0.62
Abstract · 15 pages

We consider strategic facility location in Euclidean space $\mathbb R^d$, where a mechanism selects a single facility based on the reported locations of $n$ agents and seeks to minimize the maximum distance from any agent to the facility. The optimal approximation ratio of deterministic strategyproof mechanisms is $2$. Whether randomization can yield a universal constant improvement over this factor has remained a major open question. We show that for $d \geq 2$, every strategyproof-in-expectation mechanism has approximation ratio at least \[ α(\mathcal M) \ge 2 - e^{-Θ(\sqrt d)} - O\left(n^{-2/(d-1)}\right). \] Therefore, no strategyproof-in-expectation mechanism can guarantee a $(2-\varepsilon)$-approximation uniformly over all $n$ and $d$, for any universal constant $\varepsilon>0$.

0.38

Breaking the 4-Approximation Barrier in Strategyproof Two-Facility Location

cs.GT ·2026-08-10 ·Mengfan Ma, Bo Peng
theoryhighly cited similarity 0.61
Abstract · 23 pages, 1 figure

We study strategyproof mechanism design without transfers for the two-facility location problem in metric spaces. A mechanism selects two facility locations based on agents' reported locations; each agent incurs her distance to the nearer facility, and the objective is to minimize the expected social cost. A mechanism is strategyproof if no agent ever benefits from misreporting her location. The best approximation ratio achieved by a randomized strategyproof mechanism has been $4$, attained by the Proportional mechanism of Lu, Sun, Wang, and Zhu (EC 2010), and the best lower bound has been $1.045$, due to Lu, Wang, and Zhou (WINE 2009). Neither bound has moved since then, even on the line $\mathbb{R}$. We improve both bounds. Our main result is a randomized strategyproof mechanism with approximation ratio $11/3 \approx 3.667$ on every Ptolemaic metric space, a rich class containing all Euclidean spaces. The mechanism randomizes between the Proportional mechanism and a new mechanism that we call Global Pair. Global Pair draws an unordered pair of agents with probability proportional to their distance and opens facilities at their reported locations. Although Global Pair and Proportional each have approximation ratio $4$, the two mechanisms attain their worst-case approximation ratios on complementary instances. Randomizing between them balances these complementary weaknesses and breaks the $4$-approximation barrier. On the lower-bound side, we construct a new two-profile instance that yields a lower bound of $(1+\sqrt{2})/2 \approx 1.207$, improving upon the previous lower bound of $1.045$.

0.50

Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings

cs.DS cs.CCcs.DMmath.CO ·2026-10-21 ·Frank Kammer, Sandra Kiefer, Johannes Meintrup
top venuetheory similarity 0.61
Abstract · Full version of a paper accepted for publication at SODA 2027. 37 pages, 3 figures

Temporal graphs are graphs whose edge relation changes in discrete time steps. The Temporal Exploration Problem (TEXP) asks for a temporal walk that visits all vertices. We show that every connected temporal graph with $n$ vertices can be explored in $O(qn\log^3(n))$ time steps, where $q$ is the number of vertex color classes induced by the 2-dimensional Weisfeiler-Leman (2-WL) coloring. For small $q$, our bound substantially improves on the known worst-case bound of $Θ(n^2)$ in general connected temporal graphs. A corresponding walk can be constructed in deterministic polynomial time. The upper bound is complemented by lower bounds of $Ω(n\log(n))$ when $q$ is constant and $Ω(qn)$ when $1 \leq q \leq n$. We also apply our techniques to the Temporal Rendezvous Problem (TRP), in which two agents that do not communicate have to meet on a vertex of the temporal graph. Our exploration algorithm yields that, with only polynomial-time computational power, the agents can meet in $O(n\log^3(n))$ time steps, leaving a gap of only $\log^2(n)$ to the known lower bound. Dogeas, Erlebach, Kammer, Meintrup, and Moses Jr. [ICALP'24] have shown an $O(rn^{1+ε})$ bound for TEXP, for every fixed $ε> 0$, where $r$ is the number of orbits, and an $O(n^{1+ε})$ bound for TRP. Both results require superpolynomial computation time. Our contribution improves upon these results in several ways. First, the dependence on $n$ in the upper bounds on the number of time steps is decreased from $n^{1+ε}$ to $n\log^3(n)$ for both TEXP and TRP. Second, for TEXP, we bound the number of time steps linearly by the parameter q, which is efficiently computable and upper bounded by $r$. Third, we provide novel deterministic polynomial-time algorithms for both TEXP and TRP.

0.42

Byzantine Resilience of Robot Gathering under Round-Robin Scheduling

cs.DC ·2026-11-17 ·Fabian Frei, Yuichi Sudo, Koichi Wada
theory similarity 0.60
Abstract

We study deterministic gathering of $n$ anonymous, oblivious mobile robots in the plane under round-robin scheduling with rigid movement, in the presence of $f$ Byzantine robots. Robots observe all robot positions with their multiplicities, while their local coordinate systems may change adversarially between activations. The goal is for all correct robots to gather at a single point in finite time and remain there forever. We analyze ToMax, a simple algorithm that moves to a point of maximum multiplicity and stays still if and only if its current position is the unique maximum. We prove that ToMax achieves gathering whenever $f\le\lfloor\sqrt{n}/2\rfloor$, establishing an $Ω(\sqrt{n})$ lower bound on the achievable Byzantine resilience.

0.13