BriefGPT.xyz
Jul, 2023
基于拟阵约束的k次次模最大化的快速算法
Fast algorithms for k-submodular maximization subject to a matroid constraint
HTML
PDF
Shuxian Niu, Qian Liu, Yang Zhou, Min Li
TL;DR
应用阈值减小算法最大化满足 matroid 约束的 k-次模函数，提出逼近算法来最大化满足单调和非单调 k-次模函数，并提供了关于时间复杂度的结果，同时还介绍了针对总大小约束的快速算法。
Abstract
In this paper, we apply a
threshold-decreasing algorithm
to maximize $k$-submodular functions under a
matroid constraint
, which reduces the query complexity of the algorithm compared to the greedy algorithm with
→