Algorithm Design Based On Linear Programming

This thesis mainly discussed a class of covering problem on the graph by using the linear programming method.Based on the general linear programming model of this class of covering problem,we specifically study the mixed domination problem and the length bounded multiway cut problem.For the mixed domination problem,we design a3-approximation algorithm,and for the length bounded multiway cut problem,we design a-approximation algorithm.A mixed domination set of a graph is a set of vertices and edges,thus for every edge or vertex in the graph,if it is not in the mixed domination set,it must be adjacent or incident to at least on vertex or edge in the set.The mixed domination problem is to find a mixed domination set with minimum cardinality.The weighted mixed domina-tion problem is a generalization of the mixed domination set problem,where a weightis set to each vertex and a weight0)is set to each edge,and the problem is to find a mixed domination set for minimum weight.When the weights satisfy?₀),we call this problem vertex prior weighted mixed domination problem.Few approximation results are known for the vertex prior weighted mixed domination problem,and the only known 2-approximation algorithm^[1]cannot be extended to the weighted version.This thesis directy get a 4-approximation algorithm of vertex prior weighted mixed domina-tion problem by establishing the relation between the mixed domination problem and the vertex cover problem.Moreover,by using the half-integral property of the optimal so-lution of relevant linear programming model in the Nemhauser and Trotter theorem,we study the connection between the Nemhauser and Trotter theorem and crown decompo-sition.And then we use these two tools design a 3-approximation algorithm for vertex prior weighted mixed domination problem.A length bounded node multiway cut is a set of vertices in a graph,such that delete this cut set,for each pair of given terminals,there is no path of length less than.The length bounded node multiway cut problem asks to find a such cut with mini-mum weights.When there are only two terminals,this problem transforms to the length bounded min cut problem,and there is a??-approximation algorithm for this problem^[2].However,the approximation algorithm for the length bounded node multiway cut prob-lem is little research.Based on the linear programming,this paper design a-approximation algorithm of length bounded node multiway cut problem by using the primal dual schema,in addition,we prove that based on the linear programming model used in this thesis,our approximation ratio is the optimal in the sense of neglecting the constant.