Design And Analysis Of Algorithms For Several Combinatorial Optimization Problems

This paper studies the approximation algorithms of some combinatorial optimization problems. We introduce the basic notions of combinatorial optimization and worst-case analysis of algorithms in Chapter 1. In the rest of the thesis, we study approximation algorithms with their worst-case analysis for four different combinatorial optimization problems.In Chapter 2, we consider the optimization versions of the 3-Partitioning and the Kernel 3-Partitioning problems. For the objective to maximize the minimum load of the m subsets, it is shown that the MLPT algorithm has worst-case ratios (3m -1) /(4m - 2) and (2m -1) /(3m - 2), respectively.In Chapter 3, we give Multifit -based algorithms for the Kernel 3-Partitioning problem. Two objectives of minimizing the maximum load and maximizing theminimum load are studied. The worst-case ratios of our algorithms are , respectively.In Chapter 4, we consider the online scheduling problem on parallel machines where jobs are arrive over time. We give an improved upper bound for the m > 2 machine case. For two machine case, we give an approximation algorithm RL with competitive ratio 11, which is better than LPT.In Chapter 5, we study the linear time approximation algorithm of the three parallel machines offline scheduling problem with objective to minimize makespan. We prove that the worst-case ratio of algorithm D is 15/13, which is better than any other approximation algorithm except polynomial time approximation scheme considering with both worst-case ratio and time complexity.