Beyond submodular maximization via one-sided smoothness

Abstract The multilinear framework for submodular maximization was developed to achieve a tight $$1-1/e$$ 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)$$ 1 2 u T ∇ 2 F ( x ) u ≤ σ · ‖ u ‖ 1 ‖ x ‖ 1 u T ∇ F ( x ) for all $$u,x\ge 0$$ u , x ≥ 0 , $$x\ne 0$$ x ≠ 0 . For $$\sigma =0$$ σ = 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$$ max f (

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.