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

DOI10.1007/978-3-030-26176-4_54OpenAlexW2963793685MaRDI QIDQ2300078

Zhenning Zhang, Yishui Wang, Bin Liu, Dongmei Zhang, Da-Chuan 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 constraintsubmodularity rationon-submodulardiminishing-return ratio

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (3)

Greedy guarantees for non-submodular function maximization under independent system constraint with applications ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint

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