arXiv preprint ·
Nearly Optimal Sparse Navigable Graphs in General Metrics
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $α\ge1$, a directed graph on $P$ is $α$-navigable if, for every pair of distinct points $s,t\in P$, the source $s$ has an outgoing neighbor $p$ with $d(p,t)<d(s,t)/α$. The objective is to minimize the number of edges. Recent independent works of Khanna, Padaki, and Waingarten (2026) and Conway et al. (2026) give $O(\log n)$-approximation algorithms and show that an $o(\log n)$ approximation is NP-hard in general. Before our work, the best known running time for such an approximation for general $α\ge1$ was $\widetilde O(\min\{n\operatorname{OPT}_α,n^{2.5}\})$, where $\operatorname{OPT}_α$ is the minimum number of edges in an $α$-navigable graph. In this paper, we give a randomized algorithm that, with high probability, runs in $\widetilde O(n^2)$ time and achieves an $O(\log n)$ approximation for every $α\ge1$. In general, these guarantees are nearly optimal up to constant factors in the approximation and polylogarithmic factors in the running time.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.