|
|
Journal of Zhejiang University SCIENCE A
ISSN 1673-565X(Print), 1862-1775(Online), Monthly
2008 Vol.9 No.10 P.1446-1450
Min-max partitioning problem with matroid constraint
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.
Key words: Matroid, Matroid partition, Worst ratio
References:
Open peer comments: Debate/Discuss/Question/Opinion
<1>
DOI:
10.1631/jzus.A071606
CLC number:
O221.7
Download Full Text:
Downloaded:
2761
Clicked:
4944
Cited:
0
On-line Access:
Received:
2007-12-08
Revision Accepted:
2008-05-30
Crosschecked: