Improved algorithms for non-submodular function maximization problem

DOI10.1016/j.tcs.2022.07.029OpenAlexW4288734880MaRDI QIDQ5970837

Zhi-cheng Liu, Xiaoyan Zhang, Jing Jin, Hong Chang, Dong-lei Du

Publication date: 1 September 2022

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.07.029

zbMATH Keywords

greedy algorithmcardinality constraintstreaming modelnon-submodular function maximizationoffline model

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• New performance guarantees for the greedy maximization of submodular set functions
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
• Maximize a monotone function with a generic submodularity ratio
• A constrained two-stage submodular maximization
• Non-submodular maximization on massive data streams
• Approximating the least core value and least core of cooperative games with supermodular costs
• Optimal Value of Information in Graphical Models
• An analysis of approximations for maximizing submodular set functions—I
• Unnamed Item

This page was built for publication: Improved algorithms for non-submodular function maximization problem