Full Text:   <1532>

CLC number: O221.7

On-line Access: 

Received: 2007-12-08

Revision Accepted: 2008-05-30

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3303

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2008 Vol.9 No.10 P.1446~1450


Min-max partitioning problem with matroid constraint

Author(s):  Biao WU, En-yu YAO

Affiliation(s):  Department of Mathematics, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   wubiao@zju.edu.cn

Key Words:  Matroid, Matroid partition, Worst ratio

Biao WU, En-yu YAO. Min-max partitioning problem with matroid constraint[J]. Journal of Zhejiang University Science A, 2008, 9(10): 1446~1450.

@article{title="Min-max partitioning problem with matroid constraint",
author="Biao WU, En-yu YAO",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Min-max partitioning problem with matroid constraint
%A Biao WU
%A En-yu YAO
%J Journal of Zhejiang University SCIENCE A
%V 9
%N 10
%P 1446~1450
%@ 1673-565X
%D 2008
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A071606

T1 - Min-max partitioning problem with matroid constraint
A1 - Biao WU
A1 - En-yu YAO
J0 - Journal of Zhejiang University Science A
VL - 9
IS - 10
SP - 1446
EP - 1450
%@ 1673-565X
Y1 - 2008
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A071606

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Babel, L., Kellerer, H., Kotov, V., 1998. The k-partitioning problem. Math. Methods Oper. Res., 47(1):59-82.

[2] Burkard, R.E., Yao, E.Y., 1990. Constrained partitioning problems. Discr. Appl. Math., 28(1):21-34.

[3] Edmonds, J., 1965. Minimum partition of a matroid into independent subsets. J. Res. NBS, 69B:67-72.

[4] Garey, M.R., Johnson, D.S., 1978. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, CA.

[5] Graham, R.L., 1969. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math., 17(2):416-429.

[6] Hwang, F.K., 1981. Optimal partitions. J. Opt. Theory Appl., 34(1):1-10.

[7] Hwang, F.K., Sun, J., Yao, E.Y., 1985. Optimal set partitioning. J. Algebr. Methods, 6(1):163-170.

[8] Lawler, E.L., 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston.

[9] Lee, C.Y., Liman, S.D., 1993. Capacitated two-parallel machines scheduling to minimize sum of job completion times. Discr. Appl. Math., 41(3):211-222.

[10] Welsh, D.J.A., 1976. Matroid Theory. Academic Press, London.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE