May, 2011
通过多线性松弛和竞争解决方案的子模函数最大化
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
Chandra Chekuri, Jan Vondrák, Rico Zenklusen
TL;DR研究了如何在不同的 packing 类型约束下,最大化定义在给定集合上的非负子模函数,提出了一个基于多线性扩展和分数解取整的算法框架,并且解决了其中的一些重要限制问题,开辟了线性和子模函数最大化的新方法。