Yet another algorithm for dense max cut: go greedy

ABSTRACT

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 simpler proof of the result from Alon, Fernandez de la Vega, Kannan, and Karpinski [1] that dense problems have sample complexity Õ (1/ε⁴). Like previous work, our results generalize to dense maximum constraint satisfaction problems.

REFERENCES

• 1: Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSPs, Journal of Computer and System Sciences, v.67 n.2, p.212-243, September 2003 [doi>10.1016/S0022-0000(03)00008-4]
• 2: Noga Alon , Eldar Fischer , Ilan Newman , Asaf Shapira, A combinatorial characterization of the testable graph properties: it's all about regularity, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132555]
• 3: Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225140]
• 4: W. Fernandez de la Vega, MAX-CUT has a randomized approximation scheme in dense graphs, Random Structures & Algorithms, v.8 n.3, p.187-198, May 1996 [doi>10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U]
• 5: Alan M. Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combinatorica, 19(2):175--220, 1999.
• 6: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Theory