Fast bicriteria streaming algorithms for submodular cover problem under noise models
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F25%3A10256810" target="_blank" >RIV/61989100:27240/25:10256810 - isvavai.cz</a>
Result on the web
<a href="https://www.sciencedirect.com/science/article/pii/S0920548924000527?via%3Dihub" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0920548924000527?via%3Dihub</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.csi.2024.103883" target="_blank" >10.1016/j.csi.2024.103883</a>
Alternative languages
Result language
angličtina
Original language name
Fast bicriteria streaming algorithms for submodular cover problem under noise models
Original language description
The Submodular Cover (SC) problem has attracted the attention of researchers because of its wide variety of applications in many domains. Previous studies on this problem have focused on solving it under the assumption of a non-noise environment or using the greedy algorithm to solve it under noise. However, in some applications, the data is often large-scale and brings a noisy version, so the existing solutions are ineffective or not applicable to large and noisy data. Motivated by this phenomenon, we study the Submodular Cover under Noises (SCN) problem and propose two efficient streaming algorithms, which provide a solution with theoretical bounds under two common noise models, multiplicative and additive noises. The experimental results indicate that our proposed algorithms not only provide the solution with a high objective function value but also outperform the state-of-the-art algorithm in terms of both the number of queries and the running time.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Computer Standards and Interfaces
ISSN
0920-5489
e-ISSN
1872-7018
Volume of the periodical
91
Issue of the periodical within the volume
leden 2025
Country of publishing house
US - UNITED STATES
Number of pages
10
Pages from-to
nestránkováno
UT code for WoS article
001265395800001
EID of the result in the Scopus database
—