Research On Approximation Algorithms For Combinatorial Optimization Problems Based On Graph Structure

Combinatorial optimization considers the properties and solutions of combinatorial optimization problems.It organically combines combinatorics and graph theory,approximate algorithms and computational complexity,and belongs to the interdisciplinary subject of operations research and computer science.It has a wide application background in economic management,production scheduling,engineering technology and military.Especially in recent decades,human society increasingly needs to rationally arrange the use of limited resources,manpower and time to complete tasks as well as possible and achieve goals.With the rapid development of information science and network technology,especially the innovative development of the Internet and its derived Internet of Things and social networks,which change the world and human life style,the models,theories and methods of combinatorial optimization research are becoming more and more abundant.The application of combination optimization in the environment has penetrated into all aspects of production and life: including artificial intelligence,logistics cloud distribution,sharing economic system and intelligent transportation.Graph is one of the basic and important concepts in discrete mathematics.It is composed of several nodes and edges connecting these points,and depicts many objects and some specific relations between them.Graph theory is a branch of mathematics with graph as its research object.Graph theory itself is a part of applied mathematics,which has a strong application background and is widely used in operations research,computer science and coding theory.In this thesis,we study the combinatorial optimization problems with graph structure,such as parallel machine scheduling problem,hypergraph partition problem,routing problem and location problem.The main work is as follows:In Chapter 2,we study the problem of scheduling three identical parallel machines with capacity constraints.We describe the relationship between the 3-cut problem and the three parallel machine scheduling problem.Furthermore,for the three-parallel machine scheduling problem whose optimization objective is to minimize the weighted total completion time with capacity constraints,an approximate algorithm is designed by using complex semidefinite programming relaxation and random rounding techniques,and the approximate ratio is 1.3346.In Chapter 3,we study the maximum 3-cut problem with limited unbalance of hypergraphs.Large-scale networks are characterized by complex structure and large amount of resources,so it is difficult to describe the network structure well by classical graph model.For example,when dealing with color images,the binary adjacency structure is insufficient.In order to characterize practical problems,it requires a high-dimensional hypergraph structure to represent.This chapter uses complex semidefinite programming to complete the mathematical modeling of this problem.Based on complex semidefinite programming relaxation techniques,hyperplane random rounding,random flipping and greedy strategy,we design a constant factor approximation algorithm for this problem and complete a detailed theoretical analysis.The corresponding approximation ratios are obtained for different non-equilibrium parameters.In Chapter 4,we study two kinds of generalized models of traveling salesman problem:general cluster routing problem and general traveling salesman path problem.For the general cluster routing problem,we use the classical Christofides algorithm and combinatorial techniques to design 21/11-approximation and 2.75-approximation algorithms respectively according to whether the starting vertex and end vertex are given in the cluster.For the general traveling salesman path problem,we use the linear programming rounding technique and the graph structure narrow cut to design the 1.6277-approximate algorithm.In Chapter 5,we study a special type of connected facility location problem: the stochastic rent or buy problem with submodular penalty.In this problem,the customer sets appear randomly with a certain probability,and the rent or buy costs are different at different stages.In addition,for some distant customers,in order to reduce the total cost,the system can give them certain compensation without providing corresponding services.Using linear programming rounding and primal-dual techniques,we first design a 5-approximation algorithm for this problem,and then,based on the improved approximation algorithm for Steiner tree problem,we further improve the approximation ratio of this problem to 4.39.