arXiv preprint ·
Hardness of Online Directed Steiner Network
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
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
Succinct Representation of Search Trees on Trees
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
The Complexity of Computing Class Probabilities in BID Probabilistic Databases
Union-Find with Constant-Time Deletions Across the Optimal Worst-Case Tradeoff
A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees
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.