摘要
In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.
In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms--the modified Edmonds＇ matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.
基金
Project (No. 10671177) supported by the National Natural Science Foundation of China
