An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties

In this paper, we consider the group prize-collecting Steiner tree problem with submodular penalties (GPCST-SP problem). In this problem, we are given an undirected connected graph G = (V, E) with a pre-specified root r and a partition V = {V-0, V-1, ..., V-k} of V with r is an element of V-0. Assume c : E -> R+ is an edge cost function and p : 2(V) -> R+ is a submodular penalty function, where R+ is the set of nonnegative real numbers. For a group V-i is an element of V, we say it is spanned by a tree if the tree contains at least one vertex of that group. The goal of the GPCST-SP problem is to find an r-rooted tree that minimizes the costs of the edges in the tree plus the penalty cost of the subcollection S containing these groups not spanned by the tree. Our main result is a 2I-approximation algorithm for the problem, where I = max{vertical bar V-i vertical bar vertical bar i = 0, 1, 2, ..., k}.

Automated summary

This paper considers the group prize-collecting Steiner tree problem with submodular penalties. The goal of the problem is to find an r-rooted tree that minimizes the costs of the edges in the tree plus the penalty cost of the subcollection not spanned by the tree. The main result is a 2I-approximation algorithm for the problem.