A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
From MaRDI portal
Publication:2175059
DOI10.1007/s10878-020-00558-4zbMath1442.90130OpenAlexW3011965773MaRDI QIDQ2175059
Xiaoying Qu, Ding-Zhu Du, Suning Gong, Jiazhu Fang, Yan Feng, Qingqin Nong
Publication date: 27 April 2020
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-020-00558-4
Related Items (6)
An optimal streaming algorithm for non-submodular functions maximization on the integer lattice ⋮ A binary search double greedy algorithm for non-monotone DR-submodular maximization ⋮ Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint ⋮ A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function ⋮ Profit maximization in social networks and non-monotone DR-submodular maximization ⋮ Improved algorithms for non-submodular function maximization problem
Cites Work
- Unnamed Item
- Maximizing a class of submodular utility functions
- Submodular functions: from discrete to continuous domains
- Submodular Function Maximization on the Bounded Integer Lattice
- Maximizing Non-monotone Submodular Functions
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
- Deterministic Algorithms for Submodular Maximization Problems
- Submodular Maximization with Cardinality Constraints
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Online submodular welfare maximization: Greedy is optimal
This page was built for publication: A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
