Key points are not available for this paper at this time.
Abstract 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 (83+43+), 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.
Liu et al. (Fri,) studied this question.