A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity

DOI10.1016/j.tcs.2023.114254MaRDI QIDQ6118307

Ruiqi Yang, Dong-lei Du, Shengminjie Chen, Wenguo Yang, Yapu Zhang

Publication date: 23 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

decompositionDR-submodular maximizationthreshold decrease algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• 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
• Substitute goods, auctions, and equilibrium
• Maximizing monotone submodular functions over the integer lattice
• Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
• A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
• Submodular Function Maximization on the Bounded Integer Lattice
• Maximizing Non-monotone Submodular Functions
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• Constrained Submodular Maximization via a Nonsymmetric Technique
• Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
• Fast algorithms for maximizing submodular functions
• Novel algorithms for maximum DS decomposition
• Improved deterministic algorithms for non-monotone submodular maximization

This page was built for publication: A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity