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...
Lưu vào:
| Tác giả chính: | , , |
|---|---|
| Định dạng: | Bài trích |
| Ngôn ngữ: | English |
| Nhà xuất bản: |
World Scientific Publishing
2022
|
| Chủ đề: | |
| Truy cập trực tuyến: | https://www.worldscientific.com/doi/abs/10.1142/S0217595922500130 https://dlib.phenikaa-uni.edu.vn/handle/PNK/5767 https://doi.org/10.1142/S0217595922500130 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| 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.881002 |