Submodular Maximization Subject to a Knapsack Constraint Under Noise Models

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 c...

Full description

Saved in:
Bibliographic Details
Published in:Asia-Pacific journal of operational research 2022-12, Vol.39 (6)
Main Authors: Ha, Dung T. K., Pham, Canh V., Hoang, Huan X.
Format: Article
Language:English
Subjects:
Algorithms
Constraint modelling
Explosions
Greedy algorithms
Maximization
Multiplication
Noise
Operations research
Optimization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ([Formula: see text]) 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 [Formula: see text] to show the performances of the proposed algorithms.
ISSN:0217-5959
1793-7019
0217-5959
DOI:10.1142/S0217595922500130