A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization 3: Fractional Double Greedy on the Multilinear Extension Achieves 1/2 of the OptimumResearch Paper
Unconstrained submodular maximization (USM) asks for a subset of a finite ground set maximizing a nonnegative submodular function . It contains Max-Cut, Max-DiCut and maximum facility location as special cases, and it is the basic subproblem of many constrained submodular maximization algorithms. Because is given only through a value oracle,…