Abstract 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.
CHEN Feng, YAO En-yu. EXACT ALGORITHM FOR BIN COVERING[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2001, 2(3): 241-246.
