





















Given a natural number $k\ge 2$, we consider the $k$-submodular cover problem ($k$-SC). The objective is to find a minimum cost subset of a ground set $\mathcal{X}$ subject to the value of a $k$-submodular utility function being at least a certain predetermined value $τ$. For this problem, we design a bicriteria algorithm with a cost at most $O(1/ε)$ times the optimal value, while the utility is at least $(1-ε)τ/r$, where $r$ depends on the monotonicity of $g$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。