On The Algorithms Of Some Combinatorial Optimization Problems On The Network

This thesis studies some combinatorial optimization problems on the networks,including two multiple Hamiltonian path problems,a multiple depots vehicle routing problems with capacity 2 and a resource reallocation problem in the SDN networks.We study the properties of these combinatorial optimization problems,and provide some algorithms based on these properties.For the first two multiple Hamiltonian path problems,we develop several Christofides-like heuristics and analyze the approximation ratio.For the multiple depots capacited vehicle routing problems with capacity 2,we show that the problem is polynomial solvable when the number of non-base depots is a constant.Otherwise,it is NP-hard.And for the general case,we provide an approximation algorithm.For resource reallocation problem in the SDN networks,we transform it into an equivalent sparse optimization problem over a set of linear inequalities.We also develop several algorithms and perform detailed numerical experiment to show the effectiveness and efficiency.This thesis includes six chapters:In Chapter one,we first introduce the problems studied in this thesis.Then we summary the research background and related works.We also describe some preliminary notion and conception used in this work.In Chapter two,we study the multiple depots multiple terminals Hamiltonian path problem.When the number of salesmen equals k,and the distance between the vertices satisfies the triangle inequality,we provide a Christofides-like heuristic with tight approximation ratio 2-1/2k+1,which runs in O(|V|3).Further,we develop a divide-and-conquer framework to further improve the performs of the 2-1/2k+1-approximation algorithm.For any fixed k and ∈,the framework can reduce the approximation ratio to 5/3+∈ within a polynomial time.In Chapter three,we study the multiple depots Hamiltonian path problem.When the number of salesmen equals k,and the distance between the vertices satisfies the triangle inequality,we provide a 2-1/k-approximation Christofides-like heuristic.Moreover,we show that the approximation ratio is tight.Besides,we also develop an improved algorithms with constant approximation ratio 5/3,which runs in polynomial time when k is fixed.For the special case when all the salesmen start from the same depot,we show that the improved algorithm achieves the approximation ratio of 3/2.Finally,we develop a divide-and-conquer framework to further improve the performs of previous Christofideslike heuristic.For any fixed k and e,the framework can reduce the approximation ratio to 3/2+∈ within a polynomial time.In Chapter four,we study a special case of the multiple depots capacited vehicle routing problem,where all the customers have unit demand and all the vehicles have capacity two.We propose a new structure called T-bone.With the help of this new structure,we show that the problem is polynomial solvable when the number of non-base depots is a constant.Otherwise,it is NP-hard.And for the general case We provide a 3-2/p+1-approximation algorithm.In Chapter five,we study the resource reallocation problem in the SDN networks.We transform it into an equivalent sparse optimization problem over a set of linear inequalities.This problem is the natural generalization of the problem of finding the sparse solution of linear equations.We present three heuristics with different techniques:primal greedy heuristic,dual greedy heuristic and iterative dual greedy heuristic.The computational results show that the proposed heuristics remarkably outperform other heuristics in both the quality of solution and the computational efficiency.In Chapter six,we conclude the whole thesis and provide some potential future research directions.