Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems

We consider the following general network design problem on directed graphs. The input is an asymmetric metric (V,c), root r*∈ V, monotone submodular function f:2Vrightarrow ℝ_+ and budget B. The goal is to find an r*-rooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasi-polynomial time O(fraclog kloglog k)-approximation algorithm for this problem, where k≤ |V| is the number of vertices in an optimal solution. To the best of our knowledge, this is the first non-trivial approximation ratio for this problem. As a consequence we obtain an O(fraclog2 kloglog k)-approximation algorithm for directed (polymatroid) Steiner tree in quasi-polynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved O(fraclog2 kloglog k)-approximation algorithms for the single-source buy-at-bulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio [GLL19]. Our algorithm has the advantage of being deterministic and faster: the runtime is exp(O(log n, log1+ε k)). For polymatroid Steiner tree and single-source buy-at-bulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first non-trivial approximation ratio. All our approximation ratios are tight (up to constant factors) for quasi-polynomial algorithms.