| Applied Mathematics |
|
|
|
|
| Min-max partitioning problem with matroid constraint |
| Biao WU, En-yu YAO |
| Department of Mathematics, Zhejiang University, Hangzhou 310027, China |
|
|
|
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.
|
|
Received: 08 December 2007
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
