The Study On Two Combinatorial Optimization Problems

The Chinese Postman Problem is an important combinatorial optimization problem, which involves finding a shortest closed circuit that visits each edge at least once in a given network. This problem was originally formulated and studied by the Chinese mathematician Guan Meigu in1960. Since then, this problem as well as its many variants has attracted many research efforts for more than5decades, obtaining a lot of rich and deep results. In the field of computational complexity theory, the Chinese Postman Problem is a well-known problem in complexity class P, which means that the optimal solution of the problem can be achieved by a polynomial time algorithm. In this thesis, we firstly gave a clear description of the Chinese Postman Problem through the notion of T-joins and introduced different kinds of algorithms for efficiently solving the problem. Secondly, we studied the so-called the largest sum of cycle packing problem on undirected graphs and we gave a complete proof of the equivalence relation between this problem and the Chinese Postman Problem in the sense that we can make efficient use of any algorithm that solves any one of the problems in order to solve the other one. Finally, based on the results we have got related to the Chinese Postman Problem and the largest sum of cycle packing problem, we introduced a concept of maximum Quasi-Euler circuit and have made some relevant research, pointing out the possible direction for future study.Parallel Machine Scheduling is a classic combinatorial optimization problem, and the Scheduling Problem with Rejection can be viewed as a generalization of it. As is well-known, the Parallel Machine Scheduling is NP-hard, so the Scheduling Problem with Rejection is also NP-hard, and hence neither of them can be solved exactly in polynomial time unless NP=P. In this thesis, we presented a2-approximation algorithm within strongly polynomial time for the Scheduling Problem with Rejection, and provided a tight example for our approximation algorithm, showing our analysis for the algorithm is best possible. Moreover, we presented a polynomial time approximation scheme with running time of O(nm O(1/2ε)+mn2) for the Scheduling Problem with Rejection.