Submodular Maximization Subject to a Knapsack Constraint Under Noise Models

Dung T. K. Ha (), Canh V. Pham and Huan X. Hoang ()
Additional contact information
Dung T. K. Ha: Faculty of Information Technology, University of Engineering and Technology, Vietnam National University, Hanoi, 144 Xuan Thuy Street, Cau Giay District, Hanoi 10000, Vietnam
Canh V. Pham: ORLab, Faculty of Computer Science, Phenikaa University, Yen Nghia Ward, Ha Dong District, Hanoi, 12116, Vietnam
Huan X. Hoang: Faculty of Information Technology, University of Engineering and Technology, Vietnam National University, Hanoi, 144 Xuan Thuy Street, Cau Giay District, Hanoi 10000, Vietnam

Asia-Pacific Journal of Operational Research (APJOR), 2022, vol. 39, issue 06, 1-26

Abstract: The field of Submodular Maximization subject to a Knapsack constraint has recently expanded to a variety of application domains, which is facing some challenges such as data explosions or additional conditions. There exist plenty of objective functions that cannot be evaluated exactly in many real cases unless they are estimated with errors. It leads to solving the problem under noise models. Somewhat surprisingly, Submodular Maximization subject to a Knapsack constraint under Noise models (SMKN) has never been discussed a lot before. Hence, in this paper, we consider the problem with two kinds of noise models which are addition and multiplication. Inspired by the traditional Greedy algorithm, we first propose a Greedy algorithm under Noises with provable theoretical bounds. In order to find the solution when input data are extremely large, we then devise an efficient streaming algorithm that scans only a single pass over the data and guarantees theoretical approximations. Finally, we conduct some experiments on Influence Maximization problem under knapsack constraint, an instance of SMKN to show the performances of the proposed algorithms.

Keywords: Submodular; knapsack constraint; approximation algorithm; noises (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922500130
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:39:y:2022:i:06:n:s0217595922500130

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922500130

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 ().