A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

We consider the Unconstrained Submodular Maximization problem in which we are given a non-negative submodular function f: 2 N → ℝ +, and the objective is to find a subset S ⊆ 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 MaxCut, 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 et al. [11]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem. Our method might seem counterintuitive, since it is known that the greedy algorithm fails to achieve any bounded approximation factor for the problem.

Authors

• Niv Buchbinder
• Moran Feldman
• Joseph Naor
• Roy Schwartz 0002

Keywords

• Approximation algorithms
• Approximation methods
• Optimized production technology
• Algorithm design and analysis
• Greedy algorithms
• Linear programming
• Computer science
• Linear Time
• Submodular Maximization
• Unconstrained Maximization
• Non-negative
• Hardness
• Greedy Approach
• Max-Cut
• Tight Approximation
• Linear-time Algorithm
• Changes In Values
• Objective Function
• True Value
• Time Complexity
• Estimation Algorithm
• Feasible Solution
• Value Of Solution
• Simulated Annealing
• Rest Of This Section
• Output Of Algorithm
• Local Search Algorithm
• Side Of Inequality
• Algorithm Execution
• Submodular Functions