A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem

In this paper,we consider the generalized prize-collecting Steiner forest problem,extending the prize-collecting Steiner forest problem.In this problem,we are given a connected graph G=(V,E)and a set of vertex sets V={V1,V2,…,Vl}.Every edge in E has a nonnegative cost,and every vertex set in V has a nonnegative penalty cost.For a given edge set F⊆E,vertex set Vi∈V is said to be connected by edge set F if Vi is in a connected component of the F-spanned subgraph.The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is minimized.Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.

TRANSFORMATIONS FOR THE PRIZE-COLLECTING STEINER TREE PROBLEM AND THE MAXIMUM-WEIGHT CONNECTED SUBGRAPH PROBLEM TO SAP

Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.

Algorithms for the Prize-Collecting k-Steiner Tree Problem

In this paper,we study the prize-collecting k-Steiner tree(PCkST) problem.We are given a graph G=(V,E) and an integer k.The graph is connected and undirected.A vertex r ∈ V called root and a subset R?V called terminals are also given.A feasible solution for the PCkST is a tree F rooted at r and connecting at least k vertices in R.Excluding a vertex from the tree incurs a penalty cost,and including an edge in the tree incurs an edge cost.We wish to find a feasible solution with minimum total cost.The total cost of a tree F is the sum of the edge costs of the edges in F and the penalty costs of the vertices not in F.We present a simple approximation algorithm with the ratio of 5.9672 for the PCkST.This algorithm uses the approximation algorithms for the prize-collecting Steiner tree(PCST) problem and the k-Steiner tree(kST) problem as subroutines.Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to 5.

An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties

In this paper,we consider the generalized prize-collecting Steiner forest problem with submodular penalties(GPCSF-SP problem).In this problem,we are given an undirected connected graph G=(V,E)and a collection of disjoint vertex subsets V={V_(1),V_(2),…,V_(l)}.Assume c:E→R_(+)is an edge cost function andπ:2^(V)→R_(+)is a submodular penalty function.The objective of the GPCSF-SP problem is to find an edge subset F such that the total cost including the edge cost in F and the penalty cost of the subcollection S containing these Vi not connected by F is minimized.By using the primal-dual technique,we give a 3-approximation algorithm for this problem.