In June, I wrote about my work on using spectral partitioning to approximate Max Cut.
I have now posted a revised paper with a couple new things.
One is an improved analysis due to Moses Charikar, of the algorithm described in the June paper. Moses shows that if one starts from a graph in which the optimum cuts a fraction of edges, then the algorithm cuts at least a fraction of edges (and also at least half of the edges). Cutting more than a fraction of edges is Unique-Games-hard. Optimizing the fraction
we see that the approximation ratio of the algorithm is always at least .
The second new result answers a question raised by an anonymous commenter in June: what about Max Cut Gain?
Max Cut Gain is the variant of Max Cut in which we count the number of cut edges minus the number of uncut edges. This means that if the Max Cut optimum is , then the Max Cut Gain is . (The name comes from the fact that we are looking at how much we can gain compared to a random solution that cuts half of the edges.)
Assuming hardness of Unique Games, this problem does not allow constant approximation, and the best one can hope for is to cut a fraction of edges in graphs in which the optimum is . This is achieved by an algorithm by Charikar and Wirth.
In my paper I show the considerably weaker result that, using a recursive spectral partitioning algorithm, it is possible to cut a fraction of edges in graphs in which the optimum is .
The main result (which gives the basic step in the recursive procedure) is a randomized rounding process such that if we are given a vector such that
we can find a vector such that
We do so by finding a distribution over vectors such that
The main difficulty in achieving (3) is that the terms and can be positive and negative, and so it is not sufficient to establish that is well approximated by . Indeed, suppose that we could prove that for every we have ; then it could be that when , and when . Then it could be the case that (1) is positive while (3) is negative.
It seems nearly unavoidable, then, to construct a rounding scheme such that is exactly equal, up to a scaling factor, to .
This, however, is problematic, because then we would have be proportional to , while we need it to be proportional to in order to derive (3). This means that the approximation that we get depends on the ratio between the smaller and larger , which can be arbitrarily bad. (A similar difficulty arises in the analysis of the algorithm of Charikar and Wirth.)
A more careful analysis is to establish that, for a scaling factor , we have
because then we have, from (1),
If can then establish that, for some , we have , then we deduce
We show the existence of a distribution satisfying the above equations with .