A TIGHT LINEAR TIME (1/2)-APPROXIMATION FOR UNCONSTRAINED SUBMODULAR MAXIMIZATION

被引:144
作者
Buchbinder, Niv [1 ]
Feldman, Moran [2 ]
Naor, Joseph
Schwartz, Roy [3 ]
机构
[1] Tel Aviv Univ, Stat & Operat Res Dept, IL-69978 Tel Aviv, Israel
[2] Ecole Polytech Fed Lausanne, Sch Comp & Commun Sci, CH-1015 Lausanne, Switzerland
[3] Princeton Univ, Dept Comp Sci, Princeton, NJ 08540 USA
关键词
submodular functions; approximation algorithms; linear time; APPROXIMATION ALGORITHMS; CUT; MINIMIZATION; LOCATION;
D O I
10.1137/130929205
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function f : 2(N) -> R+, and the objective is to find a subset S subset of N maximizing f(S). This is one of the most basic submodular optimization problems, having a wide range of applications. Some well-known problems captured by Unconstrained Submodular Maximization include Max-Cut, Max-DiCut, and variants of Max-SAT and maximum facility location. We present a simple randomized linear time algorithm achieving a tight approximation guarantee of 1/2, thus matching the known hardness result of Feige, Mirrokni, and Vondrak [SIAM J. Comput., 40 (2011), pp. 1133-1153]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem.
引用
收藏
页码:1384 / 1402
页数:19
相关论文
共 40 条
[31]  
Kulik A, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P545
[32]   Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case [J].
Lee, H ;
Nemhauser, GL ;
Wang, YH .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 94 (01) :154-166
[33]   MAXIMIZING NONMONOTONE SUBMODULAR FUNCTIONS UNDER MATROID OR KNAPSACK CONSTRAINTS [J].
Lee, Jon ;
Mirrokni, Vahab S. ;
Nagarajan, Viswanath ;
Sviridenko, Maxim .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 23 (04) :2053-2078
[34]  
Lee J, 2009, LECT NOTES COMPUT SC, V5687, P244
[35]  
Minoux M., 1978, Proceedings of the 8th IFIP Conference on Optimization Techniques, P234, DOI 10.1007/BFb0006528
[36]   Approximating the least core value and least core of cooperative games with supermodular costs [J].
Schulz, Andreas S. ;
Uhan, Nelson A. .
DISCRETE OPTIMIZATION, 2013, 10 (02) :163-180
[37]   Submodular Approximation: Sampling-Based Algorithms and Lower Bounds [J].
Svitkina, Zoya ;
Fleischer, Lisa .
PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2008, :697-706
[38]   Gadgets, approximation, and linear programming [J].
Trevisan, L ;
Sorkin, GB ;
Sudan, M ;
Williamson, DP .
SIAM JOURNAL ON COMPUTING, 2000, 29 (06) :2074-2097
[39]  
VONDRAK J., 2012, COMMUNICATION
[40]   Symmetry and approximability of submodular maximization problems [J].
Vondrak, Jan .
2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :651-670