Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

被引:99
作者
Lee, Jon [1 ]
Sviridenko, Maxim [1 ]
Vondrak, Jan [2 ]
机构
[1] IBM TJ Watson Res Ctr, Yorktown Hts, NY 10598 USA
[2] IBM Almaden Res Ctr, San Jose, CA 95120 USA
关键词
matroid; submodular function; approximation algorithm; ALGORITHM; APPROXIMATIONS;
D O I
10.1287/moor.1100.0463
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
Submodular function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including max cut in digraphs, graphs, and hypergraphs; certain constraint satisfaction problems; maximum entropy sampling; and maximum facility location problems. Our main result is that for any k >= 2 and any epsilon > 0, there is a natural local search algorithm that has approximation guarantee of 1/(k+epsilon) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves upon the 1/(k+1)-approximation of Fisher, Nemhauser, and Wolsey obtained in 1978 [Fisher, M., G. Nemhauser, L. Wolsey. 1978. An analysis of approximations for maximizing submodular set functions-II. Math. Programming Stud. 8 73-87]. Also, our analysis can be applied to the problem of maximizing a linear objective function and even a general nonmonotone submodular function subject to k matroid constraints. We show that, in these cases, the approximation guarantees of our algorithms are 1/(k-1+epsilon) and 1/(k+1+1/(k-1)+epsilon), respectively. Our analyses are based on two new exchange properties for matroids. One is a generalization of the classical Rota exchange property for matroid bases, and another is an exchange property for two matroids based on the structure of matroid intersection.
引用
收藏
页码:795 / 806
页数:12
相关论文
共 35 条
[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]   On local search for weighted k-set packing [J].
Arkin, EM ;
Hassin, R .
MATHEMATICS OF OPERATIONS RESEARCH, 1998, 23 (03) :640-648
[4]  
Berman P., 2000, Nordic Journal of Computing, V7, P178
[5]  
Brylawski T. H., 1973, Discrete Mathematics, V6, P333, DOI 10.1016/0012-365X(73)90064-2
[6]  
Calinescu G., 2010, SIAM J COMP IN PRESS
[7]  
Calinescu G, 2007, LECT NOTES COMPUT SC, V4513, P182
[8]   Greedy local improvement and weighted set packing approximation [J].
Chandra, B ;
Halldórsson, MM .
JOURNAL OF ALGORITHMS, 2001, 39 (02) :223-240
[9]   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
[10]   LOCATION OF BANK ACCOUNTS TO OPTIMIZE FLOAT - ANALYTIC STUDY OF EXACT AND APPROXIMATE ALGORITHMS [J].
CORNUEJOLS, G ;
FISHER, ML ;
NEMHAUSER, GL .
MANAGEMENT SCIENCE, 1977, 23 (08) :789-810