2022/11/14 by Qimeng Yu, Si̇mge Küçükyavuz, Yu, Qimeng +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2211.07726
openalex publication_date 2022/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
DR-submodular functions encompass a broad class of functions which are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide the complete convex hull of such an epigraph, which, surprisingly, turns out to be polyhedral. We propose a polynomial-time exact separation algorithm for our proposed valid inequalities, with which we first establish the polynomial-time solvability of this class of mixed-integer nonlinear optimization problems.