BriefGPT.xyz
Sep, 2023
非单调$k$-次模最大化问题的鲁棒近似算法在背包约束下
Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint
HTML
PDF
Dung T. K. Ha, Canh V. Pham, Tan D. Tran, Huan X. Hoang
TL;DR
提出了两个确定性近似算法来解决非单调k-次模极大化问题,其在查询复杂度仅为O(nk)的情况下提供了常数近似比率,比现有算法少使用了Omega(log n)数量的查询。
Abstract
The problem of
non-monotone
$k$-submodular maximization under a
knapsack constraint
($\kSMK$) over the ground set size $n$ has been raised in many applications in machine learning, such as data summarization, inf
→