Monotone submodular maximization over the bounded integer lattice with cardinality constraints

DOI10.1142/S1793830919500757zbMath1427.90243OpenAlexW2979322470WikidataQ127112397 ScholiaQ127112397MaRDI QIDQ5207510

Qiufen Ni, Chuanhe Huang, Weili Wu, Lei Lai, Chang-hong Lu

Publication date: 2 January 2020

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830919500757

zbMATH Keywords

submodular functioninteger latticecardinality constraintdiminishing return property

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

A short proof for stronger version of DS decomposition in set function optimization ⋮ A binary search double greedy algorithm for non-monotone DR-submodular maximization ⋮ Profit maximization in social networks and non-monotone DR-submodular maximization ⋮ On strict submodularity of social influence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing a class of submodular utility functions
• Submodular function minimization
• Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
• Maximizing monotone submodular functions over the integer lattice
• Constrained submodular maximization via greedy local search
• Submodular functions and optimization.
• A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
• Submodular Function Maximization on the Bounded Integer Lattice
• Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
• Maximizing Non-monotone Submodular Functions
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Deterministic Algorithms for Submodular Maximization Problems
• The Data-Correcting Algorithm for the Minimization of Supermodular Functions
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Submodular Maximization with Cardinality Constraints
• Fast algorithms for maximizing submodular functions
• A Unified Continuous Greedy Algorithm for Submodular Maximization