Improved algorithms for non-submodular function maximization problem

DOI10.1007/978-3-030-93176-6_17MaRDI QIDQ5918732zbMATH OpenOpenAlexFDO

Authors Hong Chang, Donglei Du, Xiaoyan Zhang, Zhicheng Liu

Publication date 1 July 2022

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-93176-6_17

zbMATH Keywords

non-submodular maximizationstreaming modeluniform matroid

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Recommendations

• Maximizing a non-decreasing non-submodular function subject to various types of constraints
• Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
• Non-submodular maximization with matroid and knapsack constraints
• Fast algorithms for maximizing monotone nonsubmodular functions
• A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice

Cites work

• Non-submodular maximization on massive data streams
• Parametric monotone function maximization with matroid constraints
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem

Cited in

(3)

• Maximizing a non-decreasing non-submodular function subject to various types of constraints
• Online algorithms for BP functions maximization
• Improved algorithms for non-submodular function maximization problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918732)