A Quasi-Polynomial Algorithm for Submodular Tree Orienteering in Directed Graphs
share
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:2^V 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( k/ 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 a simple O(^2 k/ 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.
READ FULL TEXT