Min-max partitioning problem with matroid constraint

被引：0

作者：

Wu, Biao ^{[1
]}

Yao, En-yu ^{[1
]}

机构：

[1] Zhejiang Univ, Dept Math, Hangzhou 310027, Peoples R China

来源：

JOURNAL OF ZHEJIANG UNIVERSITY-SCIENCE A | 2008年 / 9卷 / 10期

基金：

中国国家自然科学基金;

关键词：

matroid; matroid partition; worst ratio;

D O I：

10.1631/jzus.A071606

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

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.

引用

页码：1446 / 1450

页数：5

共 50 条

[31] Min-Max Spaces and Complexity Reduction in Min-Max Expansions
Stephane Gaubert
William M. McEneaney
Applied Mathematics & Optimization, 2012, 65 : 315 - 348
[32] An exact algorithm for Min-Max hyperstructure equipartition with a connected constraint
Tan, Tunzi
Gao, Suixiang
Mesa, Juan A.
COMPUTERS & OPERATIONS RESEARCH, 2017, 87 : 183 - 193
[33] A min-max cult algorithm for graph partitioning and data clustering
NERSC Division, Lawrence Berkeley National Laboratory, University of California, Berkeley, CA 94720, United States
不详
不详
Proc. IEEE Int. Conf. Data Min. ICDM, (107-114): : 107 - 114
[34] A min-max cut algorithm for graph partitioning and data clustering
Ding, CHQ
He, XF
Zha, HY
Gu, M
Simon, HD
2001 IEEE INTERNATIONAL CONFERENCE ON DATA MINING, PROCEEDINGS, 2001, : 107 - 114
[35] Dichotomy algorithm for solving weighted min-max programming problem with addition-min fuzzy relation inequalities constraint
Lin, Haitao
Yang, Xiaopeng
COMPUTERS & INDUSTRIAL ENGINEERING, 2020, 146
[36] The min-max problem for evaluating the form error of a circle
Jywe, WY
Liu, CH
Chang, KY
PROCEEDINGS OF THE FIRST INTERNATIONAL SYMPOSIUM ON INSTRUMENTATION SCIENCE AND TECHNOLOGY, 1999, : 202 - 206
[37] MIN-MAX SPANNING TREE PROBLEM AND SOME EXTENSIONS
CAMERINI, PM
INFORMATION PROCESSING LETTERS, 1978, 7 (01) : 10 - 14
[38] Min-max inequalities and the timing verification problem with max and linear constraints
Cheng, YP
Zheng, DZ
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2005, 15 (02): : 119 - 143
[39] ON A MIN-MAX THEOREM
CHEN FANGQI
AppliedMathematics:AJournalofChineseUniversities(SeriesB), 1997, (03) : 43 - 48
[40] Optimal tilt lifting of beams as a min-max problem
Tin-Loi, F
Lee, Z
STRUCTURAL AND MULTIDISCIPLINARY OPTIMIZATION, 2004, 26 (1-2) : 160 - 168

← 1 2 3 4 5 →