A Primal Dual Approximation Algorithm for the Multicut Problem in Trees with Submodular Penalties

摘要

In this paper, we introduce the multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in trees and vertex cover with submodular penalties. We present a combinatorial 3-approximation algorithm, based on the primal-dual scheme for the multicut problem in trees.