A Linear-Expected-Time Algorithm for Max Cut on Sparse Random Graphs
Phase Transitions in Computation and Reconstruction
March 10, 2005 11:30 AM to 11:50 AM
Speakers:
|
 |
Summary: |
We show that a maximum cut, in an n-vertex random graph with edge
density 1/n or less, can be found in linear expected time. We actually prove
the same result for "semi-random" instances of "Max 2-CSP", and throughout
the scaling window, i.e., for clause/variable densities up to 1/n+O(n^{-4/
3}). The algorithm itself solves arbitrary instances, with running time
exponential in the "excess" of edges over vertices. The linear bound on
expected running time follows from analyzing the upper tail of the
distribution of the excess of a component of a random graph. The
analysis of excess uses branching processes and Brownian motion-like random
walks,and has some interesting aspects. |
Keywords: |
Phase Transition;Computation;Reconstruction |
|
|
