Approximation algorithms for Node-weighted Steiner Problems: Digraphs with Additive Prizes and Graphs with Submodular Prizes
share
In the budgeted rooted node-weighted Steiner tree problem, we are given a graph G with n nodes, a predefined node r, two weights associated to each node modelling costs and prizes. The aim is to find a tree in G rooted at r such that the total cost of its nodes is at most a given budget B and the total prize is maximized. In the quota rooted node-weighted Steiner tree problem, we are given a real-valued quota Q, instead of the budget, and we aim at minimizing the cost of a tree rooted at r whose overall prize is at least Q. For the case of directed graphs with additive prize function, we develop a technique resorting on a standard flow-based linear programming relaxation to compute a tree with good trade-off between prize and cost, which allows us to provide very simple polynomial time approximation algorithms for both the budgeted and the quota problems. For the budgeted problem, our algorithm achieves a bicriteria (1+ϵ, O(1/ϵ^2n^2/3lnn))-approximation, for any ϵ∈ (0, 1]. For the quota problem, our algorithm guarantees a bicriteria approximation factor of (2, O(n^2/3lnn)). Next, by using the flow-based LP, we provide a surprisingly simple polynomial time O((1+ϵ)√(n)lnn)-approximation algorithm for the node-weighted version of the directed Steiner tree problem, for any ϵ>0. For the case of undirected graphs with monotone submodular prize functions over subsets of nodes, we provide a polynomial time O(1/ϵ^3√(n)logn)-approximation algorithm for the budgeted problem that violates the budget constraint by a factor of at most 1+ϵ, for any ϵ∈ (0, 1]. Our technique allows us to provide a good approximation also for the quota problem.
READ FULL TEXT