A new greedy strategy for maximizing monotone submodular function under a cardinality constraint

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

zbMATH Keywords

greedy algorithmcurvaturecardinality constraintsubmodular maximization

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Related Items (1)

Constraint generation approaches for submodular function maximization leveraging graph properties

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