Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985
We show that a maximum cut of a random graph below the giant-component threshold can be found in linear space and linear expected time by a simple algorithm. In fact, the algorithm solves a more general class of problems, namely binary 2-variable constraint satisfaction problems. In addition to Max Cut, such Max 2-CSPs encompass Max Dicut, Max 2-Lin, Max 2-Sat, Max-Ones-2-Sat, maximum independent set, and minimum vertex cover. We show that if a Max 2-CSP instance has an 'underlying' graph which is a random graph G ∈ script G sign(n,c/n), then the instance is solved in linear expected time if . Moreover, for arbitrary values (or functions) c > 1 an instance is solved in expected time ; in the 'scaling window' c = 1 + λ n-1/3 with λ fixed, this expected time remains linear. Our method is to show, first, that if a Max 2-CSP has a connected underlying graph with vertices and edges, then O(n 2(m-n)/2} is a deterministic upper bound on the solution time. Then, analysing the tails of the distribution of this quantity for a component of a random graph yields our result. Towards this end we derive some useful properties of binomial distributions and simple random walks. © 2006 Cambridge University Press.
Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985
M. Shub, B. Weiss
Ergodic Theory and Dynamical Systems
Andrew Skumanich
SPIE Optics Quebec 1993
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering