求解下模福利问题的一种随机算法及其性能保证

摘要

给出了求解下模福利问题最大值的一种随机算法,并证明了所给算法的性能保证为 1-e-1.%A new randomized algorithm for maximizing submodular welfare problem is presented, and that the performance guarantee of this algorithm is 1-e-1 is proved.