BriefGPT.xyz
May, 2024
指导式组合算法用于次模最大化
Guided Combinatorial Algorithms for Submodular Maximization
HTML
PDF
Yixin Chen, Ankur Nath, Chunli Peng, Alan Kuhnle
TL;DR
本研究通过开发导向测量连续贪心算法的组合类算法,实现子模函数限制下的近似比率,同时进行去随机化处理和几乎线性时间算法的开发。
Abstract
For constrained, not necessarily monotone submodular maximization, guiding the measured
continuous greedy algorithm
with a local search algorithm currently obtains the state-of-the-art
approximation factor
of 0.4
→