Unconstrained submodular maximization captures many NP-hard combinatorial optimization problems, including Max-Cut, Max-Di-Cut, and variants of facility location problems. Recently, presented a surprisingly simple linear time randomized greedy-like online algorithm that achieves a constant approximation ratio of 1 2, matching optimally the hardness result of . Motivated by the algorithm of , we introduce a precise algorithmic model called double-sided myopic algorithms. We show that while the algorithm of can be realized as a randomized online double-sided myopic algorithm, no such deterministic algorithm, even with adaptive ordering, can achieve the same approximation ratio. With respect to the Max-Di-Cut problem, we relate the algorithm and our myopic framework to the online algorithm and inapproximation of Bar-Noy and Lampis.
Our motivation is the double-sided greedy algorithms of Buchbinder that we wish to formalize. Independently, Bar-Noy and Lampis @cite_45 gave a @math deterministic online greedy algorithm for the Max-Di-Cut problem matching the deterministic approximation obtained by Buchbinder for all unconstrained non-monotone submodular maximization problems. Interestingly, their algorithm is shown to be the de-randomization of the simple @math random-cut algorithm! Bar-Noy and Lampis give an improved @math approximation for Max-Di-Cut when restricted to DAGs. Furthermore, they provide a precise online model with respect to which this approximation bound is essentially optimal.
@cite_45
2179494254
We consider the Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function @math , and the objective is to find a subset @math maximizing @math . This is one of the most basic submodular optimization problems, having a wide range of applications. Some well-known problems captured by Unconstrained Submodular Maximization include Max-Cut, Max-DiCut, and variants of Max-SAT and maximum facility location. We present a simple randomized linear time algorithm achieving a tight approximation guarantee of 1 2, thus matching the known hardness result of Feige, Mirrokni, and Vondrak [SIAM J. Comput., 40 (2011), pp. 1133--1153]. Our algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem.