Max Cut Approximation Algorithm

[saadahmed42]

Hi,
I'm trying to compute the approximation ratio of the following randomized algorithm for finding the max-cut of a graph.

The Max-cut problem as I understand it is that you divide the vertices of a graph G(V,E) into two sets V_1 and V_2 such that the number of edges connecting a vertex in V_1 and a vertex in V_2 is maximized.

The approximation algorithm that I'm analyzing for solving the max cut problem is as follows:

Assign each vertex to V_1 or V_2 randomly with equal probability.

That's it.


Now, an approximation algorithm as I understand it is the ratio between the performance of the approximation algorithm and performance of the optimal algorithm. I can compute the performance of the approximation - but I don't know what the optimal solution for the problem is and how to compute it's performance.

Any help would be greatly appreciated.


Thanks.
Saad

[DragForce]

Normally, if one can't provide an optimal algorithm for a problem but still wants to evaluate the quality of a proposed heuristic algorithm the following method is used:

Define some upper bound on the optimal solution. As a trivial upper bound you can use number of edges in the graph. Then, find proportion between the output of your algorithm and that upper bound. The ratio defines the quality of your algorithm.

To improve the ratio you may either improve your heuristic or come up with a better upper bound or find an optimal solution.