A Quasi-Polynomial Algorithm for Submodular Tree Orienteering in Directed Graphs.
Rohan Ghuge, Viswanath Nagarajan · arXiv (Cornell University) · 2018
We consider the following general network design problem on directed graphs. The input is an asymmetric metric $(V,c)$, root $r\in V$, monotone submodular function $f:2^V \xrightarrow{} \mathbb{R}_+$ 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 quasi-polynomial time $O(\frac{\log k}{\log\log k})$-approximation algorithm for this problem, where $k\le |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 a simple $O(\frac{\log^2 k}{\log\log k})$-approximation algorithm for directed (polymatroid) Steiner tree in quasi-polynomial time. For the usual directed Steiner tree problem, this matches the best previous result known. For the polymatroid generalization, our result improves prior results by a logarithmic factor. Our approximation ratio is tight for quasi-polynomial algorithms under certain complexity assumptions.