Reviews: Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization

The paper is about maximizing non-monotone continuous submodular functions on the hypercube [0,1] n. The main result of the paper is an algorithm that provides a tight (1/2-eps)-optimal solution using O(n 2/eps) complexity. The algorithm is built on the double-greedy algorithm proposed by Buchbinder et al for maximizing non-monotone submodular set functions, however, it turns out that a number of novel ideas have to be added to extend the algorithm to continuous submodular functions (e.g. the coordinate-wise zero-sum game strategy to decide the value of the final solution at each coordinate). A 1/2-optimal algorithm was already known for DR-submodular functions and a 1/3-opt efficient algorithm was known for continuous submodular functions, both based on the double-greedy method, however, I find the case of general continuous submodular functions much more difficult than maximizing non-monotone DR-submodular functions. All in all, after a careful read, I find the results of the paper quite novel and I recommend acceptance.