sets S, T, each with O(n) vertices, such that every pair of vertices x ∈ S and y ∈ T is at least 1/ log n apart. In our example, this means that there are large sets of vertices S, T such that every pair of vertices x ∈ S and y ∈ T lies on opposite sides of at least 1/ log n fraction of the cuts. By a simple averaging argument, since every cut separating S from T has at least an edges, there must be a pair of vertices x and y which are connected by a path of cost at most 1/a.

We are not quite done yet, since we must actually exhibit a pair of vertices that lie on opposite sides of b fraction of cuts. So far, we have only exhibited a pair of closely vertices that lie on opposite sides of 1/ log n fraction of the cuts. The last step in the proof is to piece together a sequence of O ( log n ) pairs to obtain a pair of vertices that lie on opposite sides of b fraction of the cuts, and which are connected by a path of cost O ( log n / a ). To carry out this last step, we actually have to appeal to the internal structure of the proof establishing the existence of the antipodal sets S and T. This “chaining” argument has found other uses in other research in the last few years.

3. 1. the duality connection

There is a notion of duality for SDP and an expander flow turns out to be a type of dual solution to the semidefinite program outlined in Figure 1. Thus as in all settings involving duality, a dual solution can be seen as “certifying” a lower bound on the optimal value of the primal. Thus, the expander flow is a way to certify a lower bound on the size of the optimal cut.

4. ahk aLGoRithm foR finDinG exPanDeR fLows

Arora, Hazan, and Kale (AHK) ² managed to turn the 1-round game described in the previous section into an efficient algorithm, specifically, by designing efficient strategies for the toll player and the routing player.

During the AHK algorithm, the routing player maintains a traffic graph and the toll player maintains edge tolls and cut prizes as above. At each round, the toll player does spectral partitioning on the current traffic graph, finds a sparse cut in it, and places some nonzero prize on it. (This requires adjusting down the prizes on existing cuts because the net sum has to stay 1.) The routing player then finds pairs of nodes as mentioned in Section 3—namely, a pair whose prize money is at least b and whose edge-toll-distance is smallest—and adds the resulting paths to the traffic graph (again, this requires adjusting the values of the existing edges in the traffic graph because the total degree of each node in the traffic graph is constant). The game finishes when the traffic graph is a b-expander, a condition that can be checked by the spectral methods mentioned earlier.

With some work, each round can be implemented to run in O(n²) time. The key to the performance of the algorithm lies in the fact that the readjustment of tolls can be done in a way so that the game finishes in O(log n) rounds, which results in a running time of O(n² log n). This uses a feasible version of von Neumann’s min– max theorem that Arora, Hazan, and Kale (in a separate survey paper³) call the multiplicative weight update rule:

the toll player updates tolls on the edges and cuts accordingly by always multiplying or dividing by a fixed power of the quantity ( 1 + e) where e is small. (This updated rule has been around for five decades and been rediscovered in many settings including convex optimization and machine learning; see³ for a survey.) They set up the game with some care so that the toll on an edge at any time is an exponential function of the flow routed through it, which is where the logarithmic bound on the number of rounds comes from.

4. 1. faster algorithms for semidefinite programs Motivated by the above discoveries, Arora and Kale⁴ have designed a new combinatorial approach for computing approximate solutions to SDPs. This is important because solving SDPs usually is quite slow in practice (though polynomial time in theory). Their idea is to define a multiplicative weight update rule for matrices, which is used in a primal-dual fashion to get a quick approximation. The algorithm has some formal similarities to the “random walk” idea described in Section 5. They obtain the best running times known for a host of SDP-based approximation algorithms. For finding cuts, one may prefer the algorithms of the next section on account of simplicity, though the Arora–Kale approach is comparable in running time and approximation factor. Again, we refer the reader to the survey. ³

5. towaRD PRacticaL aLGoRithms

So far, we have described a framework for improving the approximation factor or the quality of cut found by graph-partitioning algorithms. In this section, we describe an algorithm of Khandekar, Rao, and Vazirani¹² that modifies the framework to design a much faster algorithm for graph partitioning—its running time is bounded by a small number of calls to a single commodity max-flow subroutine. As in the AHK algorithm from the previous section, the new algorithm may also be viewed as a contest between two players, though the underlying game, called the cut-matching game, is slightly different.

The object of the cut-matching game, played over a sequence of rounds, is to construct an expanding traffic graph. Initially, the traffic graph is the empty graph on n vertices. In each round, the cut player chooses a bisection of the vertex set, and the matching player specifies a perfect matching that pairs up vertices across the bisection. The edges of the perfect matching are added to the traffic graph, and the game continues until the traffic graph has expansion greater than 1. The goal of the cut player is to minimize the number of rounds before the game ends. The matching player, of course, tries to prolong the game.

How does the cut-matching game relate to partitioning a given graph G(V, E)? Given a bisection, the matching player tries to find a perfect matching that can be routed through G(V, E) with small congestion. This is accomplished by performing a single max-flow computation, and the corresponding min-cut is a candidate partition of G(V, E) (see Figure 5).

The cut player uses a novel spectral type algorithm,