.png){kind=icon}
.png){kind=icon}
Return
Efficient Deterministic Bicriteria Approximation Algorithms for k-Submodular Cover Problem
.png){kind=icon}
PRE
AI
DOI：10.1142/s0217595926500144.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study the k-Submodular Cover (kSC) problem over a ground set V of size n, where the goal is to find k disjoint subsets of V with minimum cost such that a k-submodular utility function exceeds a given threshold. This problem generalizes the well-known Sub-modular Cover (SC) problem and has numerous applications in artificial intelligence and combinatorial optimization. However, existing approximation algorithms for kSC may not run in polynomial time. In this work, we propose two bicriteria approximation algorithms that not only improve the performance guarantees but also significantly reduce the query complexity compared to the state-of-the-art algorithms.
Keywords:
Combinatorial optimization
approximation algorithm
k-submodular cover
Journal
A
IF:
1
Papers:
58
Citations:
0