Free and Latest article publishing for websites and ezines!

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.

Recommended Articles from the Basic Sciences Category:

Most Viewed ScienceArticles in the Basic Sciences Category:

  1. Inflow Performance Relationship and Application for Low Permeability-Defomed Media Reservoir
  2. Numerical Simulation of Engine Con-rod Fracture Splitting Process and Analysis on Effect Factors
  3. An Evaluation of Ecotourism Characteristics in Nature Reserves and Tourism Impacts on Breeding Behavi
  4. Research on Seed Germination Ecology
  5. Oil and Gas Geological Condition and Prospect Evaluation in the Peripheral Down-Faulted Basins Group
  6. Investigation of Hyperspectral Remote Sensing Data Classification Using Multiple Classifiers Combinat
  7. Roles of RNA Secondary Structure in Dengue Virus C Gene and Capsid Protein in Viral Replication
  8. Research on the Electro-optic Effect of Silicon
  9. Lagrange Interpolation and Hermite Interpolation Along the Algebraic Manifold
  10. Study on the Function of miR-483 and miR-34a
  11. Krylov Subspace Methods for Large Matrix Eigenvalue and Linear System Problems
  12. Effect of Iron on Growth and Lipid Accumulation in Several Microalgae with Different Metabolic Type
  13. Study on the Degradative Characteristics and Pathway of PAHs Degrading Bacteria
  14. Role of RIG-I-like Receptors during Type I Interferon Response Induced by Dengue Virus Infection
  15. Key Parameters of Photobioreactor Cultivation of Macroalgal Cells


© 2004-2009 Latest-Science-Articles.com - All Rights Reserved Worldwide.