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.
@cite_45: We investigate a natural online version of the well-known Maximum Directed Cut problem on DAGs. We propose a deterministic algorithm and show that it achieves a competitive ratio of @math . We then give a lower bound argument to show that no deterministic algorithm can achieve a ratio of @math for any ?>0 thus showing that our algorithm is essentially optimal. Then, we extend our technique to improve upon the analysis of an old result: we show that greedily derandomizing the trivial randomized algorithm for MaxDiCut in general graphs improves the competitive ratio from 4 to 3, and also provide a tight example.
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.