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

arXiv: https://arxiv.org/abs/1812.01768 · HTML: https://mlsanity.com/paper/1812.01768/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2018.

## Built on by (most cited first, 1 of 1)

- [Computation and Bribery of Voting Power in Delegative Simple Games](https://mlsanity.com/paper/2104.03692/) (2021)

## Abstract (arXiv)

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.