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

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název periodika

Mathematics

ISSN

2227-7390

e-ISSN

2227-7390

Svazek periodika

10

Číslo periodika v rámci svazku

20

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

19

Strana od-do

nestrankovano

Kód UT WoS článku

000875226800001

EID výsledku v databázi Scopus

—