Cover Image

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
Main Authors: Dung, T. K. Ha, Canh, V. Pham, Huan, X. Hoang
Format: Bài trích
Language:English
Published: World Scientific Publishing 2022
Subjects:
Submodular
Knapsack constraint
Online Access:https://www.worldscientific.com/doi/abs/10.1142/S0217595922500130
https://dlib.phenikaa-uni.edu.vn/handle/PNK/5767
https://doi.org/10.1142/S0217595922500130
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-5767
record_format dspace
spelling oai:localhost:PNK-57672022-08-17T05:54:54Z Submodular Maximization Subject to a Knapsack Constraint Under Noise Models Dung, T. K. Ha Canh, V. Pham Huan, X. Hoang Submodular Knapsack constraint 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. 2022-05-05T07:26:22Z 2022-05-05T07:26:22Z 2022 Bài trích https://www.worldscientific.com/doi/abs/10.1142/S0217595922500130 https://dlib.phenikaa-uni.edu.vn/handle/PNK/5767 https://doi.org/10.1142/S0217595922500130 en World Scientific Publishing
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic Submodular
Knapsack constraint
spellingShingle Submodular
Knapsack constraint
Dung, T. K. Ha
Canh, V. Pham
Huan, X. Hoang
Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
description 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.
format Bài trích
author Dung, T. K. Ha
Canh, V. Pham
Huan, X. Hoang
author_facet Dung, T. K. Ha
Canh, V. Pham
Huan, X. Hoang
author_sort Dung, T. K. Ha
title Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
title_short Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
title_full Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
title_fullStr Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
title_full_unstemmed Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
title_sort submodular maximization subject to a knapsack constraint under noise models
publisher World Scientific Publishing
publishDate 2022
url https://www.worldscientific.com/doi/abs/10.1142/S0217595922500130
https://dlib.phenikaa-uni.edu.vn/handle/PNK/5767
https://doi.org/10.1142/S0217595922500130
_version_ 1751856315040268288
score 8.891145

Similar Items