Maximizing k-submodular functions under budget constraint: applications and streaming algorithms

Canh V. Pham (), Quang C. Vu (), Dung K. T. Ha (), Tai T. Nguyen () and Nguyen D. Le ()
Additional contact information
Canh V. Pham: Phenikaa University
Quang C. Vu: People’s Security Academy
Dung K. T. Ha: University of Engineering and Technology, Vietnam National University
Tai T. Nguyen: University of Engineering and Technology, Vietnam National University
Nguyen D. Le: Haiphong University

Journal of Combinatorial Optimization, 2022, vol. 44, issue 1, No 34, 723-751

Abstract: Abstract Motivated by the practical applications in solving plenty of important combinatorial optimization problems, this paper investigates the Budgeted k-Submodular Maximization problem defined as follows: Given a finite set V, a budget B and a k-submodular function $$f: (k+1)^V \mapsto \mathbb {R}_+$$ f : ( k + 1 ) V ↦ R + , the problem asks to find a solution $$\mathbf{s }=(S_1, S_2, \ldots , S_k) \in (k+1)^V $$ s = ( S 1 , S 2 , … , S k ) ∈ ( k + 1 ) V , in which an element $$e \in V$$ e ∈ V has a cost $$c_i(e)$$ c i ( e ) when added into the i-th set $$S_i$$ S i , with the total cost of $$\mathbf{s }$$ s that does not exceed B so that $$f(\mathbf{s })$$ f ( s ) is maximized. To address this problem, we propose two single pass streaming algorithms with approximation guarantees: one for the case that an element e has only one cost value when added to all i-th sets and one for the general case with different values of $$c_i(e)$$ c i ( e ) . We further investigate the performance of our algorithms in two applications of the problem, Influence Maximization with k topics and sensor placement of k types of measures. The experiment results indicate that our algorithms can return competitive results but require fewer the number of queries and running time than the state-of-the-art methods.

Keywords: k-submodular; Budget constraint; Approximation algorithm; Streaming algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00858-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-022-00858-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00858-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().