Beyond submodular maximization via one-sided smoothness

Abstract

The multilinear framework for submodular maximization was developed to achieve a tight 1 - 1 / e approximation for maximizing a monotone submodular function subject to a matroid constraint, including as special case the submodular welfare problem. The framework has a continuous optimization step (solving the multilinear extension of a submodular function) and a rounding part (rounding a fractional solution to an integral one). We extend both parts to provide a framework for a wider array of applications. The continuous part works for a more general class of continuous functions parameterized by a new smoothness parameter σ . A twice differential function F is called σ -one-sided-smooth ( σ -OSS) if its second derivatives are bounded as follows: 1 2 u T ∇ 2 F ( x ) u ≤ σ · ‖ u ‖ 1 ‖ x ‖ 1 u T ∇ F ( x ) for all u , x ≥ 0 , x ≠ 0 . For σ = 0 this includes previously studied continuous DR-Submodular functions as well as quadratics defined by copositive matrices. We give a modification of the continuous greedy algorithm which finds a solution for maximizing a monotone σ -OSS F over a polytope in the non-negative orthant; the solution approximates the optimum to within factors which are functions of σ which depend on additional properties. Interestingly, σ -OSS functions arise as the multilinear extensions of set functions associated with several well-studied diversity maximization problems: max f ( S ) = ∑ i , j ∈ S A ij : | S | ≤ k . For instance, when A ij defines a σ -semi-metric, its extension is σ -OSS. In these settings, we also develop rounding schemes to approximate the discrete problem.