Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint

DOI10.1007/s10898-021-01014-1zbMath1479.90182OpenAlexW3142764332MaRDI QIDQ2046266

Yanjun Jiang, Zhenning Zhang, Dong-lei Du, Chen-Chen Wu

Publication date: 17 August 2021

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-021-01014-1

zbMATH Keywords

submodular functioninteger latticesupermodular functioncardinality constraintthreshold greedy algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Convex programming (90C25) Linear programming (90C05) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25)

Related Items (6)

Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice ⋮ On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice ⋮ A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity ⋮ A binary search double greedy algorithm for non-monotone DR-submodular maximization ⋮ Profit maximization in social networks and non-monotone DR-submodular maximization ⋮ Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Maximization of submodular functions: theory and enumeration algorithms
• A note on maximizing a submodular set function subject to a knapsack constraint
• Maximizing monotone submodular functions over the integer lattice
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint

This page was built for publication: Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint