Full Text:
<2696>
CLC number: O221.7
On-line Access:
Received: 2007-12-08
Revision Accepted: 2008-05-30
Crosschecked: 0000-00-00
Cited: 0
Clicked: 4853
Min-max partitioning problem with matroid constraint
| |||||||||||||
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",
volume="9",
number="10",
pages="1446-1450",
year="2008",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.A071606"
}
%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
TY - JOUR
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
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.
[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
<1>