A Study Of Partitioning Problems With Matroid Constraint

Partitioning problem is one of the classical combinatorial optimization problems. Many combinatorial optimization problems can be transformed to partitioning problem, therefore, it has many application and has received many researcher's attention. Many new models come forth along with the developing of social production. In this thesis, we review the works and main results of some basic partitioning problem and introduce uniform partition problem with the matroid constraint.There are four chapters in the thesis.Chapter 1 introduces some preliminary knowledge and basic concepts in the field. In section 1.3 we introduce matroid theory briefly. In section 1.4 we review the work and main results of some basic partitioning problems.In Chapter 2, we consider the problem of partitioning a matroid into independent subsets. The objective is to minimize the weight of the heaviest subset. An approximation algorithm for the problem and an estimation of the worst-ratio for the algorithm are given.In Chapter 3, we consider the partitioning problem with partition matroid. An approximation algorithm called the Layered LPT algorithm is given and its worst case ratio is analyzed.In Chapter 4, we continue to study the partitioning problem with partition matroid. LPT algorithm is modified to fit the problem and its worst case performance is analyzed. Lower bounds of optimal solution for the min-max problem are given.Chapter 5 is the summary of the paper and some problems in the area.