Randomized approximation algorithms for monotone k-submodular function maximization with constraints

Yuying Li (), Min Li (), Yang Zhou (), Shuxian Niu () and Qian Liu ()
Additional contact information
Yuying Li: Shandong Normal University
Min Li: Shandong Normal University
Yang Zhou: Shandong Normal University
Shuxian Niu: Shandong Normal University
Qian Liu: Shandong Normal University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 4, No 11, 28 pages

Abstract: Abstract In recent years, k-submodular functions have garnered significant attention due to their natural extension of submodular functions and their practical applications, such as influence maximization and sensor placement. Influence maximization involves selecting a set of nodes in a network to maximize the spread of information, while sensor placement focuses on optimizing the locations of sensors to maximize coverage or detection efficiency. This paper first proposes two randomized algorithms aimed at improving the approximation ratio for maximizing monotone k-submodular functions under matroid constraints and individual size constraints. Under the matroid constraints, we design a randomized algorithm with an approximation ratio of $$\frac{nk}{2nk-1}$$ nk 2 n k - 1 and a complexity of $$O(rn(\text {RO}+k\text {EO}))$$ O ( r n ( RO + k EO ) ) , where n represents the total number of elements in the ground set, k represents the number of disjoint sets in a k-submodular function, r denotes the size of the largest independent set, $$\text {RO}$$ RO indicates the time required for the matroid’s independence oracle, and $$\text {EO}$$ EO denotes the time required for the evaluation oracle of the k-submodular function.Meanwhile, under the individual size constraints, we achieve an approximation factor of $$\frac{nk}{3nk-2}$$ nk 3 n k - 2 with a complexity of O(knB), where n is the total count of elements in the ground set, and B is the upper bound on the total size of the k disjoint subsets, belonging to $$\mathbb {Z_{+}}$$ Z + . Additionally, this paper designs two double randomized algorithms to accelerate the algorithm’s running speed while maintaining the same approximation ratio, with success probabilities of ( $$1-\delta $$ 1 - δ ), where $$\delta $$ δ is a positive parameter input by the algorithms. Under the matroid constraint, the complexity is reduced to $$O(n\log r\log \frac{r}{\delta }(\text {RO}+k\text {EO}))$$ O ( n log r log r δ ( RO + k EO ) ) . Under the individual size constraint, the complexity becomes $$O(k^{2}n\log \frac{B}{k}\log \frac{B}{\delta })$$ O ( k 2 n log B k log B δ ) .

Keywords: k-Submodular function; Randomized algorithms; Approximation algorithms; Matroid constraints; Individual size constraints (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01299-y 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:49:y:2025:i:4:d:10.1007_s10878-025-01299-y

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

DOI: 10.1007/s10878-025-01299-y

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 ().