Greedy algorithm for maximization of non-submodular functions subject to knapsack constraint

DOI10.1007/978-3-030-26176-4_54MaRDI QIDQ2300078zbMATH OpenOpenAlexFDO

Authors Zhenning Zhang, Bin Liu, Yishui Wang, Dongmei Zhang, Dachuan Xu

Publication date 24 February 2020

Full work available at URL https://doi.org/10.1007/978-3-030-26176-4_54

zbMATH Keywords

curvatureknapsack constraintnon-submodulardiminishing-return ratiosubmodularity ratio

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• Maximizing a monotone non-submodular function under a knapsack constraint
• Non-submodular maximization with matroid and knapsack constraints
• Greedy is good: constrained non-submodular function maximization via weak submodularity
• Greedy guarantees for non-submodular function maximization under independent system constraint with applications
• Approximation algorithm of maximizing non-submodular functions under non-submodular constraint

Cited in

(5)

• scientific article; zbMATH DE number 5670654 (Why is no real title available?)
• Greedy is good: constrained non-submodular function maximization via weak submodularity
• Fast algorithms for maximizing monotone nonsubmodular functions
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Greedy guarantees for non-submodular function maximization under independent system constraint with applications

This page was built for publication: Greedy algorithm for maximization of non-submodular functions subject to knapsack constraint

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