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 \(\sigma \) . A twice differential function F is called \(\sigma \) -one-sided-smooth ( \(\sigma \) -OSS) if its second derivatives are bounded as follows: \(\frac{1}{2}u^T\nabla ^2 F(x) u \le \sigma \cdot \frac{\Vert u\Vert _1}{\Vert x\Vert _1} u^T \nabla F(x)\) for all \(u,x\ge 0\) , \(x\ne 0\) . For \(\sigma =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 \(\sigma \) -OSS F over a polytope in the non-negative orthant; the solution approximates the optimum to within factors which are functions of \(\sigma \) which depend on additional properties. Interestingly, \(\sigma \) -OSS functions arise as the multilinear extensions of set functions associated with several well-studied diversity maximization problems: \(\max f(S) = \sum _{i,j \in S} A_{ij} : |S| \le k\) . For instance, when \(A_{ij}\) defines a \(\sigma \) -semi-metric, its extension is \(\sigma \) -OSS. In these settings, we also develop rounding schemes to approximate the discrete problem.
