Yet Another Algorithm for Dense Max Cut: Go Greedy
Claire Mathieu, Warren Schudy · 2008
We study dense instances of MaxCut and its generalizations. Following a long list of existing, diverse and often sophisticated approximation schemes, we propose taking the naïve greedy approach; we prove that when the vertices are considered in random order, our algorithms are still approximation schemes. Our algorithms may be simple, but the analysis is not. It relies on smoothing the vertices defining the partial cuts and on proving certain martingale properties. We also give a simple proof that dense problems have sample complexity O(1/ǫ 4), which improves the result of Alon, Fernandez de la Vega, Kannan, and Karpinski [1] by a log(1/ǫ) factor. Like previous work, our results generalize to dense maximum constraint satisfaction problems. 1 Introduction and main results