Approximation Algorithms For The Submodular Multicut Problems In Trees With Linear/Submodular Penalties

Multicut problem is one of the most important combinatorial optimization prob?lems,which has an important applications in the areas of telecommunications,routing,transportation and oversized integrated circuit design.Submodular functions,which have the property of decreasing marginal returns,are recognized as fundamental tools in the areas of combinatorial optimization,game theory,machine learning and various other fields.At present,the combinatorial optimization problems with submodular penalties are receiving increasing attention.In this thesis,we mainl_y study three variants of multicut problems which are asso?ciated with the submodular functions:the submodular multicut problem in trees with linear penalties,the submodular multicut problem in trees with submodular penalties and the generalized multicut problem in trees with submodular penalties.For each of these problems,we first formulate it as an integer linear program,then design a corre?sponding approximation algorithm by using the primal-dual scheme,and finally analyze the approximate ratio of the algorithm.