Non-Submodular Maximization with Matroid and Knapsack Constraints

Yijing Wang (), Donglei Du (), Yanjun Jiang and Xianzhao Zhang ()
Additional contact information
Yijing Wang: Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, P. R. China
Donglei Du: Faculty of Management, University of New Brunswick, Fredericton E3B 5A3, Canada
Yanjun Jiang: School of Mathematics and Statistics Science, Ludong University, Yantai 264025, P. R. China
Xianzhao Zhang: School of Mathematics and Statistics, Linyi University, Linyi 276005, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2021, vol. 38, issue 05, 1-22

Abstract: We investigate the problem of maximizing a γ-submodular function subject to one or multiple matroid constraints and one knapsack constraint. By the greedy local search technique, we present approximation algorithms with constant approximation ratios. When γ = 1, our model reduces to the regular submodular maximization problem investigated in the literature under the same type of constraints. Our results therefore contribute towards the line of research on constrained non-submodular function maximization.

Keywords: Non-submodular maximization; matroid; knapsack; approximation algorithm (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595921400017
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:38:y:2021:i:05:n:s0217595921400017

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595921400017

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().