You are currently browsing the monthly archive for June 2008.
More images from Saturday and Sunday after the cut. Read the rest of this entry »
In the Max Cut problem, we are given an undirected graph and we want to find a partition of the set of vertices such that as many edges as possible have one endpoint in and one endpoint in , and are hence cut by the partition.
It is easy, as recognized since the 1970s, to find a partition that cuts half of the edges and that, thus, is at least half as good as an optimal solution. No approximation better than 1/2 was known for this problem, until Goemans and Williamson famously proved that one could achieve a .878… approximation using semidefinite programming (SDP).
No other approximation algorithm achieving an approximation asymptotically better than 1/2 is known, and it seems that a fundamental difficulty is the following. Suppose we prove that a certain algorithm achieves approximation . Then, given a graph in which the optimum is, say, , the algorithm and its analysis must provide a certificate that the optimum cut in the given graph is , and there is no general technique to prove upper bounds to the Max Cut optimum of a general graph other than Semidefinite Programming. (And see here and here for negative results showing that large classes of linear programming relaxations are unable to give such certificates.)
Spectral techniques can prove upper bounds to Max Cut in certain cases (and can be seen as special cases of the upper bounds provided by the Goemans-Williamson relaxation).
In the simplified case in which is a -regular graph, let be the adjacency matrix of and be the eigenvalues of ; then it is easy to show that
where is the fraction of edges cut by an optimal solution. Unfortunately (1) does not quite have an approximate converse: there are graphs where but .
The following fact, however, is always true and well known:
- if and only if contains a bipartite connected component.
Is there an “approximate” version of the above statement characterizing the cases in which is small? Surprisingly, as far as I know the question had not been considered before.
For comparison, the starting point of the theory of edge expansion is the related fact
- if and only if is disconnected.
Which can be rephrased as:
- if and only if there is a non-empty , such that .
Cheeger’s inequality characterizes the case in which is small:
- If there is a non-empty , such that , then ;
- If then there is a non-empty , such that .
For a subset , and a bipartition of , we say that an edge fails [to be cut by] the bipartition if is incident on but it is not the case that one endpoint is in and one endpoint is in . (This means that either both endpoints are in , or both endpoints are in , or one endpoint is in and one endpoint is not in .) Then we can express the well-known fact about as
- if and only if there is and a bipartition of with zero failed edges.
In this new paper I prove the following approximate version
- If there is a non-empty , and a bipartition of with at most failed edges, then ;
- If , then there is a non-empty , and a partition of with at most failed edges.
The following notation makes the similarity with Cheeger’s inequality clearer. Define the edge expansion of a graph as
Let us define the bipartiteness ratio of as
that is, as the minimum ratio between failed edges of a partition of a set over .
Then Cheeger’s inequality gives
and our results give
This translates into an efficient algorithm that, given a graph such that , finds a set and a bipartition of such that at least a fraction of the edges incident on are cut by the bipartition. Removing the vertices in and continuing recursively on the residual graph yields a .50769… approximation algorithm for Max Cut. (The algorithm stops making recursive calls, and uses a random partition, when the partition of found by the algorithm has too many failed edges.)
The paper is entirely a by-product of the ongoing series of posts on edge expansion: the question of relations between spectral techniques to max cut was asked by a commenter and the probabilistic view of the proof of Cheeger’s inequality that I wrote up in this post was very helpful in understanding the gap between and .
Green, Tao and Ziegler, in their works on patterns in the primes, prove a general result of the following form: if is a set, is a, possibly very sparse, “pseudorandom” susbset of , and is a dense subset of , then may be “modeled” by a large set which has the same density in as the density of in .
They use this result with being the integers in a large interval , being the “almost-primes” in (integers with no small factor), and being the primes in . Since the almost-primes can be proved to be “pseudorandom” in a fairly strong sense, and since the density of the primes in the almost-primes is at least an absolute constant, it follows that the primes are “indistinguishable” from a large set containing a constant fraction of all integers. Since such large sets are known to contain arbitrarily long arithmetic progressions, as proved by Szemeredi, Green and Tao are able to prove that the primes too must contain arbitrarily long arithmetic progressions. Such large sets are also known to contain arbitrarily long “polynomial progressions,” as proved by Bergelson and Leibman, and this allows Tao and Ziegler to argue that the primes too much contain arbitrarily long polynomial progressions.
(The above account is not completely accurate, but it is not lying too much.)
As announced last October here, and here, Omer Reingold, Madhur Tulsiani, Salil Vadhan and I found a new proof of this “dense model” theorem, which uses the min-max theorem of game theory (or, depending on the language that you prefer to use, the duality of linear programming or the Hahn Banach theorem) and was inspired by Nisan’s proof of the Impagliazzo hard-core set theorem. In complexity-theoretic applications of the theorem, our reduction has polynomial complexity, while the previous work incurred an exponential loss.
After long procrastination, we recently wrote up a paper about these results.
In the Fall, we received some feedback from additive combinatorialists that while our proof of the Green-Tao-Ziegler result was technically simpler than the original one, the language we used was hard to follow. (That’s easy to believe, because it took us a while to understand the language in which the original proof was written.) We then wrote an expository note of the proof in the analyst’s language. When we were about to release the paper and the note, we were contacted by Tim Gowers, who, last Summer, had independently discovered a proof of the Green-Tao-Ziegler results via the Hahn-Banach theorem, essentially with the same argument. (He also found other applications of the technique in additive combinatorics. The issue of polynomial complexity, which does not arise in his applications, is not considered.)
Gowers announced his results in April at a talk at the Fields institute in Toronto. (Audio and slides are available online.)
Gowers’ paper already contains the proof presented in the “analyst language,” making our expository note not so useful any more; we have still posted it anyways because, by explaining how one translates from one notation to the other, it can be a short starting point for the computer scientist who is interested in trying to read Gowers’ paper, or for the combinatorialist who is interested in trying to read our paper.