Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

被引：0
作者：
Lee, Jon
Sviridenko, Maxim
Vondrak, Jan
机构：
来源：
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES | 2009年 / 5687卷
关键词：
K-SET PACKING; ALGORITHMS; APPROXIMATIONS;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：244 / 257
页数：14
相关论文
共 31 条
[1]   Pipage rounding: A new method of constructing algorithms with proven performance guarantee [J].
Ageev, AA ;
Sviridenko, MI .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2004, 8 (03) :307-328
[2]  
[Anonymous], 2003, COMBINATORIAL OPTIMI
[3]  
[Anonymous], C NUMER
[4]  
[Anonymous], SIAM J COMP IN PRESS
[5]   On local search for weighted k-set packing [J].
Arkin, EM ;
Hassin, R .
MATHEMATICS OF OPERATIONS RESEARCH, 1998, 23 (03) :640-648
[6]  
Berman P., 2000, Nordic Journal of Computing, V7, P178
[7]  
BRYLAWSKI T, 1973, DISC MATH, V67, P333
[8]  
Calinescu G, 2007, LECT NOTES COMPUT SC, V4513, P182
[9]   Greedy local improvement and weighted set packing approximation [J].
Chandra, B ;
Halldórsson, MM .
JOURNAL OF ALGORITHMS, 2001, 39 (02) :223-240
[10]   SUBMODULAR SET-FUNCTIONS, MATROIDS AND THE GREEDY ALGORITHM - TIGHT WORST-CASE BOUNDS AND SOME GENERALIZATIONS OF THE RADO-EDMONDS THEOREM [J].
CONFORTI, M ;
CORNUEJOLS, G .
DISCRETE APPLIED MATHEMATICS, 1984, 7 (03) :251-274
1234