Efficient Streaming Algorithms for Maximizing Monotone DR-Submodular Function on the Integer Lattice

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F22%3A10251981" target="_blank" >RIV/61989100:27240/22:10251981 - isvavai.cz</a>

Result on the web

<a href="https://www.mdpi.com/2227-7390/10/20/3772" target="_blank" >https://www.mdpi.com/2227-7390/10/20/3772</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/math10203772" target="_blank" >10.3390/math10203772</a>

Result language

angličtina

Original language name

Efficient Streaming Algorithms for Maximizing Monotone DR-Submodular Function on the Integer Lattice

Original language description

In recent years, the issue of maximizing submodular functions has attracted much interest from research communities. However, most submodular functions are specified in a set function. Meanwhile, recent advancements have been studied for maximizing a diminishing return submodular (DR-submodular) function on the integer lattice. Because plenty of publications show that the DR-submodular function has wide applications in optimization problems such as sensor placement impose problems, optimal budget allocation, social network, and especially machine learning. In this research, we propose two main streaming algorithms for the problem of maximizing a monotone DR-submodular function under cardinality constraints. Our two algorithms, which are called StrDRS1 and StrDRS2, have (1/2 - epsilon) , (1 - 1 /e - epsilon) of approximation ratios and O(n/epsilon log(log B/epsilon ) log k), O(n/epsilon log B), respectively. We conducted several experiments to investigate the performance of our algorithms based on the budget allocation problem over the bipartite influence model, an instance of the monotone submodular function maximization problem over the integer lattice. The experimental results indicate that our proposed algorithms not only provide solutions with a high value of the objective function, but also outperform the state-of-the-art algorithms in terms of both the number of queries and the running time.

Czech name

—

Czech description

—

Type

J_imp - 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)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Mathematics

ISSN

2227-7390

e-ISSN

2227-7390

Volume of the periodical

10

Issue of the periodical within the volume

20

Country of publishing house

CH - SWITZERLAND

Number of pages

19

Pages from-to

nestrankovano

UT code for WoS article

000875226800001

EID of the result in the Scopus database

—