Online algorithms for directed network design cannot beat exponential limits
Hardness of Online Directed Steiner Network
Data Structures and Algorithms
Summary
The problem is about connecting pairs of points in a directed network in the cheapest way possible. The authors study when these connection requests come one by one, and decisions must be made without knowing future requests. They show that no online method can do much better than a certain expanding exponential cost compared to the best offline method. This result uses ideas from algebraic coding to prove that decisions made early can’t be cheaply reused without knowing what’s coming next.
What this means in practice
- •For network designers: Understand fundamental limitations on the efficiency of online routing and connection strategies in directed networks with uncertain demands.
- •For online algorithm developers: Avoid pursuing polylogarithmic-competitive online solutions for directed Steiner network problems, as this paper proves such performance is impossible.
A theory result. No direct application yet.
Authors
Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
Abstract
In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands $(s_i,t_i)$, and asked to find a cheap subgraph connecting each terminal pair. In its online version, the demands arrive online and must be served by buying edges irrevocably. DSN is a fundamental hard problem in network design, heavily studied in both the offline and the online setting. Offline, it has a superpolylogarithmic hardness of approximation. However, offline hardness says nothing about online algorithms, which are computationally unrestricted. It has been an open question whether uncertainty itself (needing to commit to a solution without knowing future demands) rules out polylogarithmic-competitive online algorithms. In this work, we show the first such unconditional, information-theoretic hardness. Namely, we give an $\exp\!\bigl(Ω(\sqrt{\log n})\bigr)$ bound on the competitive ratio, which holds even for randomized algorithms against an oblivious adversary, and on unit-cost DAGs. Our proof uses a novel connection between online network design and algebraic coding theory. We encode requests using a hidden low-degree polynomial, whose past evaluations reveal nothing about future ones. We then use list-recovery bounds to show that an algorithm cannot make cheaply reusable decisions without knowing those future evaluations.