New upper bounds for the MAX CUT problem
DOI:
https://doi.org/10.14419/gjma.v2i4.3325Abstract
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
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.
A. Coja-Oghlan, Spectral techniques, semide¯nite programs, and random graphs, Habilitation thesis, Humboldt University Berlin, 2005.
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.
M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, JACM 42 (1995), 1115-1145.
F. Hadlock, Finding a maximum cut of a planar graph in polynomial time, SIAM Journal on Computing, 4(3): 221-225, 1975.
S. Sahni and T. Gonzalez, P -Complete Approximation Problems, Journal of the ACM, 23(3): 555-565, 1976.
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.
X. Xu, Z. Gao, K. Xu, A tighter upper bound for random MAX 2-SAT, Informatin Processing Letters 111 (2011), 115-119.
Downloads
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal''s published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).