CS Paper Radar

Optimal Non-Adaptive Vantage Point Selection

Jie Gao, Nicole Wein, Chang Wu

cs.DS ·submitted 2026-09-09 14:53 UTC · v1
theory

Abstract

We study the \emph{vantage point selection} problem, introduced by Ashvinkumar, Chowdhury, Gao, Goswami, Mitchell, and Polishchuk [WADS'25] to model the problem of estimating bottleneck capacities on the Internet. The input is a weighted undirected graph with unique shortest paths where every edge has a distinct unknown \emph{capacity}. When the algorithm \emph{queries} a vertex $v$, it reveals the minimum-capacity edge on the shortest path from $v$ to every other vertex reachable from $v$. The goal is to maximize the total number of revealed edges. The quality of an algorithm is measured by its competitive ratio against an optimal algorithm that knows all edge capacities a priori. We first consider the foundational single-query setting, where both the algorithm and the optimal algorithm are restricted to a single query. There is a trivial upper bound of $O(n)$ on the competitive ratio and the best known lower bound was $\tildeΩ(\sqrt{n})$. We provide an algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible competitive ratio is $\tildeΘ(n^{2/3})$. Furthermore, we extend our results to the general setting where the optimal algorithm is allowed $k$ queries and our algorithm is allowed $αk$ queries for $α\geq 1$. We present a randomized non-adaptive algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible expected competitive ratio for non-adaptive algorithms is the following surprisingly complex bound: $$ \tildeΘ\left( \min\left\{ \frac{n}{αk}, \max\left( \sqrt{\frac{n}α}, \frac{n^{2/3}}{αk^{1/3}} \right) \right\} \right). $$

Closest papers

Nearest neighbours by meaning across the whole index.

Sublogarithmic Online Graph Exploration

cs.DS cs.DM ·2026-11-10 ·Julia Baligacs
similarity 0.70
Abstract

We study the online graph exploration problem, in which an agent must visit every vertex of an initially unknown weighted graph on $n$ vertices and return to its starting vertex. In this model, a vertex's incident edges and their weights are revealed when it is first visited. Despite extensive research, the best known competitive guarantee for general graphs had remained $\mathcal{O}(\log n)$, a bound already established in 1977 for the greedy TSP heuristic Nearest Neighbor. Subsequent approaches, including hierarchical depth-first search (hDFS) and Blocking, achieve better guarantees on restricted graph classes but have logarithmic or worse competitive ratios on general graphs. This raises the question of whether the logarithmic barrier is inherent and Nearest Neighbor is asymptotically optimal. We answer this question in the negative by giving an $\mathcal{O}(\log n/\log \log n)$-competitive algorithm. Our algorithm is a slight modification of hDFS, and we establish its competitive guarantee with a surprisingly short proof.

0.22

A Sublogarithmic Competitive Algorithm for Online Graph Exploration

cs.DS ·2026-11-10 ·Max Klimm
similarity 0.70
Abstract

In online graph exploration, an agent must visit every vertex of an unknown weighted graph and return to its start, learning the incident edges at each vertex it visits. On $n$-vertex graphs, the best known competitive ratio has been $O(\log n)$, achieved by several algorithms, among them the hierarchical depth-first search of Megow, Mehlhorn, and Schweitzer. We give an algorithm with competitive ratio ${(2+o(1))}\ln n/\ln\ln n$ for known~$n$. Like hierarchical depth-first search, it groups the edges into geometric weight classes and searches depth-first between components of lighter edges. Unlike it, the agent tours each component along a minimum spanning tree for the original weights, so only crossings between components pay for rounding, and the base $b$ of the weight class can grow with~$n$. The leading constant $2$ is tight for our choice of base. Without knowing $n$, restarts with increasing size guesses give upper bounds with leading constant $4$ for a fixed schedule and $2$ in expectation for a randomly shifted schedule. If the weights lie in a known range $[1,2^k]$ with $k\ge4$, choosing $b=k/\log_2 k$ gives a competitive ratio of $O(k/\log k)$ without knowing $n$.

0.25

Optimal Online Weighted Connectivity Augmentation

cs.DS ·2026-10-30 ·Mohit Garg, Felix Hommelsheim, Alexander Lindermayr
theory similarity 0.70
Abstract · 32 pages, 12 figures

In the online Weighted Connectivity Augmentation Problem (WCAP), we are given a $k$-edge-connected graph on $n$ vertices and a set of additional edges, called links, with nonnegative costs. Pairs of vertices arrive one by one, and an online algorithm must immediately and irrevocably buy links so that each pair becomes $(k+1)$-edge-connected. The goal is to minimize the total cost of the purchased links. We obtain a deterministic polynomial-time $O(\log n)$-competitive algorithm for WCAP, improving the previous $O(\log^2 n)$ bound (SODA 2026). Our bound is asymptotically optimal, even for randomized algorithms in the random-order model. The general problem reduces to the case where the underlying graph is a cycle, for which link costs in $\{0,1\}$ already yield an $Ω(\log n)$ lower bound. Surprisingly, for unit costs on a cycle, we obtain a deterministic polynomial-time $4$-competitive algorithm, improving the previous $O(\log n)$ bound (SODA 2026), and prove that this ratio is optimal among deterministic algorithms. Thus, with unit costs, cycles are easier than trees, where the optimal competitive ratio is $Θ(\log n)$.

0.25

The Price of Almost Navigability

cs.DS ·2026-09-02 ·Tomer Waizer, Yoav Danieli
theory similarity 0.67
Abstract

Navigability is a fundamental property of graph-based search structures and plays an important role in the analysis of nearest-neighbor algorithms. Informally, a graph is navigable if, from any current point and toward any desired target, there is always an outgoing edge that moves strictly closer to that target. While this property provides a strong guarantee for greedy search, it can be inherently expensive: in the worst case, navigable graphs require $Ω(n^{3/2})$ edges, where $n$ is the size of the dataset. Recently, Avi and Musco introduced $(1-ε)$-almost navigability, a natural relaxation in which, from every current point, such a progress-making edge is required for almost all targets, while an $ε$ fraction of targets may fail this condition \cite{avimusco2026almost}. They showed that every dataset admits such a graph with $O(n/ε)$ edges. In this work, we prove a matching lower bound, establishing the optimality of their construction and giving a complete characterization of the sparsity achievable by almost-navigable graphs. For most values of $ε$, our hard instances lie in Euclidean spaces of polylogarithmic dimension, across the full worst-case range of $ε$, dimension $d=O(\sqrt{n}\log^{3/2} n)$ suffices. The same construction also sharpens our understanding of ordinary navigability: in the latter dimension, we exhibit datasets for which every navigable graph has $Ω(n^{3/2})$ edges. Our proof reveals a surprising connection between almost navigability and the classical Zarankiewicz problem of constructing dense graphs with limited pairwise neighborhood overlap. This connection lets us translate extremal graph constructions into hard geometric instances for navigation, linking two seemingly different notions of graph sparsity.

0.09

Breaking Two Barriers for Dynamic Planar Reachability

cs.DS ·2026-10-09 ·Adam Karczmarz, Michał Włodarczyk
top venuetheory similarity 0.67
Abstract · To appear at SODA 2027

We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if one vertex is reachable from another. The current-best online algorithm for dynamic planar reachability spends worst-case time $\widetilde{O}(n^{2/3})$ per query/update [Subramanian, ESA '93]. This can be improved to $\widetilde{O}(n^{1/2})$ in the offline setting or when the embedding is fixed [Diks and Sankowski, ESA '07]. Our contribution is twofold: 1. We present the first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting, obtaining time ${O}(n^{0.49})$ per query/update. This shows that the problem is easier than answering distance queries in a dynamic undirected planar graph, for which a conditional lower bound of $n^{1/2 - o(1)}$ is known [Abboud and Dahlgaard, FOCS '16]. Notably, this lower bound applies to both online and offline algorithms. 2. Second, in the general online setting we design a randomized data structure with amortized update and query time ${O}(n^{0.664})$. This is the first improvement upon the exponent $2/3$ in over three decades. The main engine behind our theorems is a new sparsification framework aimed at maintaining information about reachability. Specifically, we study digraphs through the lens of VC dimensionality of certain set systems. First, we design sparse reachability emulators for planar digraphs that preserve the VC dimension. Second, we utilize orderings with a low ``stabbing number'' [Chazelle and Welzl, Discrete Comput. Geom. '89] to compute subquadratic reachability emulators in subquadratic time whenever the VC dimension is bounded.

0.40

Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers

cs.DS ·2026-08-26 ·Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg, Yibin Zhao, Gernot Zöcklein
similarity 0.66
Abstract

We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pmε)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_ε(n^2)$ and worst-case query time $\widetilde{O}_ε(1)$. Thus, for dense graphs where $m = Ω(n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\widetilde{O}(n/ε)$ epochs such that every graph within an epoch is a $(1\pm O(ε))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\widetilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.

0.09

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

cs.DS ·2026-09-18 ·Anish Hebbar, Ravi Kumar, Roie Levin, Joseph, Naor +1 more
similarity 0.66
Abstract

Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study this online algorithms with a sample (OAS) model. We show a tight $O\left(\log (1/p) \cdot \log m + \log n\right)$-competitive algorithm for set cover, exponentially improving upon the $O\left(1/p \cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein. Our techniques extend to covering integer programs and non-metric facility location, also yielding tight bounds for these problems. Further, we give an $O(\log (1/p)/ \log \log (1/p))$-competitive algorithm for metric facility location, answering an open question of Argue et al. (NeurIPS'22). We then introduce and study the robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify $k$ elements of the $p$-sample. For set cover, covering integer programs, and non-metric facility location, we obtain a tight competitive ratio of $O\left(\log (k/p) \cdot \log m + \log n\right)$. For metric facility location and Steiner tree, we obtain tight competitive ratios of $O\left(\log (k/p) / \log \log (k/p) \right)$ and $O\left(\log (k/p)\right)$ respectively. To the best of our knowledge, these are the first results for robust algorithms in the OAS setting.

0.19

Online Vertex Connectivity Augmentation

cs.DS ·2026-11-11 ·Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.66
Abstract · 35 pages

Network design problems form a classic subfield of online algorithms, but almost nothing is known about their more challenging vertex-connectivity variants. We initiate the study of online vertex-connectivity network design for arbitrary demand pairs by considering the fundamental problem of connectivity augmentation. In an instance of \emph{Online Vertex Connectivity Augmentation} (OVCA), we are given a $k$-vertex-connected graph $F$ and a set of additional purchasable edges (with costs). Demand pairs $(s_1,t_1),(s_2,t_2),\dots$ then arrive online. Upon each arrival, the algorithm must irrevocably purchase edges so that $s_i$ and $t_i$ become $(k{+}1)$-vertex-connected in the union of $F$ with all edges purchased so far. Our main contribution is an $O((k+\log n)\log n)$-competitive online algorithm for OVCA. We also give an offline $O(k+\log n)$-approximation algorithm. We obtain our algorithms via a structural dichotomy on the minimum vertex cuts of $F$. We note that some dependence on $k$ in the approximation ratio is necessary -- i.e., the problem is hard to approximate within any $\mathrm{polylog}(n)$ factor independent of $k$ -- which shows a separation from the edge-connectivity setting. Finally, specializing to $k=1$, our methods yield the first polylogarithmic-competitive online algorithm for a vertex-connectivity survivable network design problem, namely an $\widetilde O(\log^3 n)$-competitive algorithm for online $\{1,2\}$-VC-SNDP (i.e., an SNDP variant where each demand pair comes with a vertex-connectivity requirement of $1$ or $2$).

0.18