A Reduction for Optimizing Lattice Submodular Functions with Diminishing\n Returns

2016/06/27 by Alina Ene, Ene, Alina, Huy L. Nguyên +1 · 4 citations
Computer Science · #Advanced Algebra and Logic #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.1606.08362

openalex publication_date 2016/06/27 · openalex created_date 2022/09/04 · openalex updated_date 2026/07/28

Abstract

A function f: \ℤ₊^E \→ \ℝ₊ is DR-submodular if\nit satisfies f( bf x + \χ_i) -f ( bf x) \≥ f( bf y + \χ_i) - f( bf\ny) for all bf x\≤ bf y, i\∈ E. Recently, the problem of maximizing\na DR-submodular function f: \ℤ₊^E \→ \ℝ₊ subject\nto a budget constraint \‖ bf x\‖₁ \≤ B as well as additional constraints\nhas received significant attention citeSKIK14,SY15,MYK15,SY16.\n In this note, we give a generic reduction from the DR-submodular setting to\nthe submodular setting. The running time of the reduction and the size of the\nresulting submodular instance depends only \logarithmically on B. Using\nthis reduction, one can translate the results for unconstrained and constrained\nsubmodular maximization to the DR-submodular setting for many types of\nconstraints in a unified manner.\n

Citations

• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

Cited by

• Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
• Discrete and Continuous Difference of Submodular Minimization
• Randomized Algorithms for Monotone Submodular Function Maximization on\n the Integer Lattice
• Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice --- Continuous Greedy Algorithm on Median Complex ---

Related

• Non-monotone DR-Submodular Function Maximization
• Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
• Maximizing Non-Monotone DR-Submodular Functions with Cardinality Constraints
• Maximizing Monotone Submodular Functions over the Integer Lattice
• On Unconstrained Quasi-Submodular Function Optimization