Beyond Submodular Maximization via One-Sided Smoothness

The multilinear framework was developed to achieve the breakthrough 1 -1/e approximation for maximizing a monotone submodular function subject to a matroid constraint, which includes the submodular welfare problem as special case. This framework has a continuous optimization part (solving the multilinear extension of a submodular set function) and a rounding part (rounding a fractional solution to an integral one). We extend both parts so that the resulting generalized framework may be used on a wider array of problems. In particular, we make a conceptual contribution by identifying a family of parameterized functions and their applications. As a running example we focus on solving diversity problems max f (S) = 1 2 i,j∈A A ij : S ∈ M, where M is matroid. These diversity functions have A ij ≥ 0 as a measure of dissimilarity of i, j, and A has 0-diagonal. This family of problems ranges from intractable problems such as densest k-subgraph, to 1 2 -approximable metric diversity problems. The multilinear extension F of such diversity functions satisfies ∇ 2 F (x) = A ≥ 0 and hence the original multilinear framework (which assumes non-positive Hessians) does not directly apply. Instead we introduce a new parameter for functions F ∈ C 2 which measures the approximability of the associated problem maxF (x) : x ∈ P , for solvable downwards-closed polytopes

for all u, x ≥ 0, x = 0. For σ = 0 this class includes previously studied classes such as continuous DR-submodular functions, and much more. For the multlinear extension of a diversity function, we show that it is one-sided σ-smooth whenever A ij forms a σ-semi-metric.

We give an Ω(1/σ)-approximation for the continuous maximization problem of monotone, normalized one-sided σ-smooth F with an additional property: non-positive third order partial derivatives. Since the multilinear extension of a diversity function has this additional property we can apply the extended multilinear framework to this family of discrete problems. This requires new matroid rounding techniques for quadratic objectives. The result is a Ω(1/σ 3/2 )approximation for maximizing a σ-semi-metric diversity function subject to matroid constraint. This improves upon the previous best bound of Ω(1/σ 2 ) and we give evidence that it may be tight. For general one-sided smooth functions, we show the continuous process gives an Ω(1/3 2σ )approximation, independent of n. In this setting, by discretizing, we present a concrete poly-time algorithm for multilinear functions that satisfy the one-sided σ-smoothness condition. We also describe a discretization for one-sided smooth functions with L-Lipschitz gradients.