Algorithms find best meeting points fast on directed graphs
When Shall We $k$ Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance
Data Structures and Algorithms
Summary
Finding the best place for two or more agents to meet on a directed graph is a tricky puzzle with different ways to measure the best spot. The authors study two main ways: one that minimizes the longest travel time for either agent, and one that minimizes the total travel time combined. They designed new algorithms to quickly approximate or exactly find these meeting points and proved limits on how fast these algorithms can be under popular complexity assumptions. They also extended their ideas to meetings involving more than two agents, revealing how the difficulty grows with the number of participants.
What this means in practice
- •For network designers: Plan efficient meeting or rendezvous points minimizing travel delays in communication or transportation networks using new meet-distance algorithms.
- •For logistics planners: Optimize coordination points for agents or vehicles with directed movement constraints using the paper’s fast approximation methods.
A theory result. No direct application yet.
Authors
Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova, Virginia Vassilevska Williams
Abstract
Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computational geometry. In this work, we use the two objectives of optimal meeting points examined in the literature to study two notions of meet-distance: $d^{\max}(u,v)$, the minimum over all meeting points $w$ of $\max(d(u,w), d(v,w))$; and $d^+(u,v)$, the minimum over all meeting points of $d(u,w) + d(v,w)$. These values measure the minimum time and minimum total distance required for two agents to meet. We initiate the fine-grained study of fundamental graph parameters under the two notions of meet-distance, namely the diameter, radius and eccentricities. For general directed graphs, we give an $\tilde{O}(m\sqrt{n})$ time algorithm for computing a 2-approximation to both notions of meet-diameter and show that this result is optimal under SETH. In contrast, we show that such a result is unattainable for the meet-radius as any finite approximation requires quadratic time under the Hitting Set Conjecture. For directed acyclic graphs, we obtain stronger results. We compute the meet$^{\max}$-diameter exactly in linear time and give a linear-time $2$-approximation for the meet$^{+}$-diameter. We complement the latter with a quadratic-time lower bound for any $(3/2-\varepsilon)$-approximation under SETH, yielding a separation between the two meet-distance objectives. Finally, we study the generalized meet-distance of $k$-tuples of vertices. For every positive integer $\ell$, we reduce the problem of $\ell$-approximating the $k$-point meet-diameter to computing an exact meet-diameter on smaller tuples, obtaining an $\ell$-approximation in time \[ O\!\left( mn+ \ell \left\lceil k^{1/\ell}\right\rceil n^{\left\lceil k^{1/\ell}\right\rceil+1} \right). \]