A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity
From MaRDI portal
Publication:6118307
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)
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
