Budgeted Out-tree Maximization with Submodular Prizes
share
We consider a variant of the prize collecting Steiner tree problem in which we are given a directed graph D=(V,A), a monotone submodular prize function p:2^V →ℝ^+ ∪{0}, a cost function c:V →ℤ^+, a root vertex r ∈ V, and a budget B. The aim is to find an out-subtree T of D rooted at r that costs at most B and maximizes the prize function. We call this problem Directed Rooted Submodular Out-tree (DRSO). Very recently, Ghuge and Nagarajan [SODA 2020] gave a quasi-polynomial-time O(log n'/loglog n')-approximation algorithm for the case in which the costs are associated to the edges, where n' is the number of vertices in an optimal solution. In this paper we give a polynomial-time algorithm for DRSO that guarantees an approximation factor of O(√(B)/ϵ^3) at the cost of a budget violation of a factor 1+ϵ, for any ϵ∈ (0,1]. The same result holds for the edge-cost case, to our knowledge this is the first polynomial-time approximation algorithm for this case. We further show that the unrooted version of DRSO can be approximated to a factor of O(√(B)) without budget violation, which is an improvement over the factor O(Δ√(B)) given in [Kuo et al.IEEE/ACM Trans. Netw. 2015] for the undirected and unrooted case, where Δ is the maximum degree of the graph. Finally, we provide some new/improved approximation bounds for several related problems, including the additive-prize version of DRSO, the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.
READ FULL TEXT