An approximation algorithm for the -prize-collecting multicut problem in trees with submodular penalties

Let $T=(V,E)$ be a tree in which each edge is assigned a cost; let P be a set of source–sink pairs of vertices in V in which each source–sink pair produces a profit. Given a lower bound K for the profit, the K -prize-collecting multicut problem in trees with submodular penalties is to determine a partial multicut M⊆ E such that the total profit of the disconnected pairs after removing M from T is at least K , and the total cost of edges in M plus the penalty of the set of still-connected pairs is minimized, where the penalty is determined by a nondecreasing submodular function. Based on the primal-dual scheme, we present a combinatorial polynomial-time algorithm by carefully increasing the penalty. In the theoretical analysis, we prove that the approximation factor of the proposed algorithm is (8/3+4/3κ+ε) , where κ is the total curvature of the submodular function and ε is any fixed positive number. Experiments reveal that the objective value of the solutions generated by the proposed algorithm is less than 130% compared with that of the optimal value in most cases.