BriefGPT.xyz
May, 2023
非单调次模约束下背包约束下的线性查询逼近算法
Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint
HTML
PDF
Canh V. Pham, Tan D. Tran, Dung T. K. Ha, My T. Thai
TL;DR
本研究提出了两种简单实用的算法逼近非单调次模最大化问题,并分析了应用于收益最大化、图像摘要、最大加权切割等三个问题的有效性。
Abstract
This work, for the first time, introduces two constant factor
approximation algorithms
with
linear query complexity
for non-monotone
submodular m
→