New upper bounds for the MAX CUT problem

  • Authors

    • Guangyan Zhou Beihang University
    2014-09-14
    https://doi.org/10.14419/gjma.v2i4.3325

  • Abstract

    Let $f_{cut}(n,cn)$ be the expectation of the value of the maximum cut of a given random graph G(n,cn) with n vertices and cn edges. We study the asymptotic change of $f_{cut}(n,cn)/cn$ as n tends to infinity with various densities c. In this paper, we provide new upper bounds by correcting the error items when applying the first moment method. Specifically, we extrapolate the region of c from c>1.386 to c>1.001.

    Keywords: MAX CUT, Upper Bound, Random Graph, First moment method.

  • References

    1. A. Bertoni, P. Campadelli, and R. Posenato, An upper bound for the maximum cut mean value, Graph-theoretic concepts in computer science (Berlin, 1997), Lecture Notes in Comput. Sci., vol. 1335, Springer, Berlin, 1997, pp. 78-84. MR 99d:68185.
    2. A. Coja-Oghlan, Spectral techniques, semide¯nite programs, and random graphs, Habilitation thesis, Humboldt University Berlin, 2005.
    3. D. Coppersmith, D. Gamarnik, M. T. Hajiaghayi, G. B. Sorkin, Random MAX SAT, random MAX CUT, and their phase transions, Random Structures Algorithms 24 (2004), 502-545.
    4. M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, JACM 42 (1995), 1115-1145.
    5. F. Hadlock, Finding a maximum cut of a planar graph in polynomial time, SIAM Journal on Computing, 4(3): 221-225, 1975.
    6. S. Sahni and T. Gonzalez, P -Complete Approximation Problems, Journal of the ACM, 23(3): 555-565, 1976.
    7. L. Trevisan, G. B. Sorkin, Madhu Sudan, and David P. Williamson, Gadgets, approximation, and linear programming, SIAM J. Comput. 29 (2000), no. 6, 2074-2097. MR 2001 j: 68046.
    8. X. Xu, Z. Gao, K. Xu, A tighter upper bound for random MAX 2-SAT, Informatin Processing Letters 111 (2011), 115-119.

  • Downloads

  • How to Cite

    Zhou, G. (2014). New upper bounds for the MAX CUT problem. Global Journal of Mathematical Analysis, 2(4), 270-275. https://doi.org/10.14419/gjma.v2i4.3325

    Received date: 2014-08-05

    Accepted date: 2014-09-06

    Published date: 2014-09-14