A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
From MaRDI portal
Publication:2141724
DOI10.1007/s10898-021-01103-1zbMath1493.90148OpenAlexW3210727690MaRDI QIDQ2141724
Cheng Lu, Wenguo Yang, Sui-Xiang Gao
Publication date: 25 May 2022
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10898-021-01103-1
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- The ellipsoid method and its consequences in combinatorial optimization
- The budgeted maximum coverage problem
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts
- A threshold of ln n for approximating set cover
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Optimal Value of Information in Graphical Models
- An analysis of approximations for maximizing submodular set functions—I
- Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
- Guess free maximization of submodular and linear sums
This page was built for publication: A new greedy strategy for maximizing monotone submodular function under a cardinality constraint