Combinatorial Approximation Algorithms for MaxCut using Random Walks

Details Combinatorial Approximation Algorithms for MaxCut using Random Walks Combinatorial Approximation Algorithms for MaxCut using Random Walks

2010-08-23

arxiv.org/abs/1008.3938v1

Computer Science

Data Structures and Algorithms

28 pages, 1 figure

Scientific paper

We give the first combinatorial approximation algorithm for Maxcut that beats the trivial 0.5 factor by a constant. The main partitioning procedure is very intuitive, natural, and easily described. It essentially performs a number of random walks and aggregates the information to provide the partition. We can control the running time to get an approximation factor-running time tradeoff. We show that for any constant b > 1.5, there is an O(n^{b}) algorithm that outputs a (0.5+delta)-approximation for Maxcut, where delta = delta(b) is some positive constant. One of the components of our algorithm is a weak local graph partitioning procedure that may be of independent interest. Given a starting vertex $i$ and a conductance parameter phi, unless a random walk of length ell = O(log n) starting from i mixes rapidly (in terms of phi and ell), we can find a cut of conductance at most phi close to the vertex. The work done per vertex found in the cut is sublinear in n.

Affiliated with

Also associated with

No associations

Rating

Combinatorial Approximation Algorithms for MaxCut using Random Walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorial Approximation Algorithms for MaxCut using Random Walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial Approximation Algorithms for MaxCut using Random Walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-393080