An Approximate Algorithm for Constrained node multicut Problem on Trees with Penalty Costs
The constrained node multicut problem with penalty costs is a new problem that builds on the restricted node multicut problem by adding a penalty cost to each terminal pair,which is not paid if the terminal pair is disconnected,but is paid otherwise.The goal is to find the minimum sum of the weight of the disconnected terminal endpoint to the selected non-terminal endpoint and the sum of the pen-alty cost of the undisconnected terminal pair.This problem is mainly restricted to the tree for research,and the restricted node multicut problem with penalty cost on the tree is converted into the restricted node multicut problem on the tree for research.Based on linear pro-gramming theory,a primal-dual algorithm is designed to solve the restricted node multicut problem on trees,and the solution obtained by the algorithm is transformed back into the solution of the restricted node multicut problem with penalty cost on trees.Finally,it is proved that the approximate value of the solution obtained by this method is 2.
NETL
NSTL
万方数据
