Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization

Norman Huang, Allan Borodin

Unconstrained submodular maximization captures many NP-hard combinatorial optimization problems, including Max-Cut, Max-Di-Cut, and variants of facility location problems. Recently…