Approximation Algorithms For The Partial Prize-Collecting Multicut Problems In Trees

Multicut problem is one of the most classical NP-hard problems in combinatorial optimization.In this thesis,we study two variants of vertex cover problems:the k-prize-collecting multicut problem in trees and the P-prize-collecting multicut problem in trees.In the k-prize-collecting multicut problem in trees,we are given an undirected tree T=(V,E),a set of m distinct vertex pairs Q={(s1,t1),...,(sm,tm)} and a parameter k with k ≤m.Every edge e in E has a nonnegative cost ce.Every pair(si,ti)in Q has a nonnegative penalty cost πi.The goal is to find a multicut M that separates at least k pairs in Q with minimum total cost including the edge cost of the multicut M and the penalty cost of the pairs not separated by M.In the P-prize-collecting multicut problem in trees,we are given an undirected tree T=(V,E),a set of m distinct vertex pairs Q={(s1,t1),...,(sm,tm)} and a positive number P called profit bound.Every edge e in E has a nonnegative cost ce.Every pair(si,ti)in Q has a nonnegative penalty cost πi and a nonnegative profit pi.The goal is to find a multicut M such that the total cost,including the edge cost of the multicut M and the penalty cost of the pairs not separated by M,is minimized and the combined profit of the vertex pairs cut by M is at least P.In this thesis,we respectively design the approximate algorithms for the k-prize-collecting multicut problem in trees and the P-prize-collecting multicut problem in trees by using the primal dual scheme and Lagrange relaxation,and prove that their approxi-mate ratios are all(4+ε),where ε is any fixed positive number.