Streaming Algorithm for Submodular Cover Problem Under Noise
Bich-Ngan T. Nguyen, Phuong N. H. Phạm, Canh V. Pham, Anh N. Su, Václav Snåšel · 2021
Submodular Cover problem has attracted the attention of researchers because of its wide variety of applications in economics, machine learning, digital marketing, and computer science. Previous studies on this problem have focused on solving it under the assumption in a non-noise environment, or using the greedy algorithm to solve under noise. However, in some applications, the data is often large scale and brings the noisy version, so the effectiveness of existing solutions is low or not applicable in large and noisy data. Motivated by this phenomenon, we study the Submodular Cover under Noise (SCN) problem and propose a single pass streaming algorithm, which provides a bicriteria approximation solution for SCN. The experiment results indicate that our algorithm provides solutions with the high value of objective functions and outperforms the-state-of-art algorithm in terms of both number of queries and running time.