described in the box below, to find a bisection in almost
linear time. It can be shown that by following this strategy
the cut player can limit the number of rounds of the game
to O(log2 n). Now the best candidate partitioning among
the O(log2 n) rounds is the output of the algorithm, and
can be shown to be within a O(log2 n) factor of the optimal
partition.
PROCEDURE: MATCHING PLAYER
input: bisection (S and V – S), of graph G.
• run a concurrent flow computation between S and V – S.
Formulate a flow problem where each node in S is a source and
each node in V – S is the sink of one unit of flow.
the goal is to satisfy each source and sink while minimizing the
maximum integral flow across any edge of G. this is a standard
single commodity flow problem.
• decompose the flow into n/2 source-sink paths to obtain the
matching:
Greedily follow a path of positive flow arcs from a source node u to
some sink. remove this path from the flow, and repeat.
• output the matching.
PROCEDURE: cUT PLAYER
input: set {M , . . . , M } of perfect matchings.
1T
1. let u0 be a random n-dimensional unit vector.
2. Fort = 1 to T
For each edge {i, j } ∈ M
t
−ut + 1 (i) = (ut (i ) + ut( j ) )/2
3. output cut (S, V – S), where
S = {i : u (i) ≤ m},
T
with m being the median value of the u (i)’s.
T
The total running time of the matching player is bounded by O(log2 n) invocations of single commodity max-flow
computations. This is the dominant term in the running
time of the algorithm, since the cut player runs in nearly
linear time.
The overall algorithm starts by invoking the cut player
with the empty set of matchings and invokes the cut player
and matching player for O(log2 n) rounds. Each invocation
of the matching player results in a candidate partition of
the graph given by the min-cut in the invocation of the
max-flow procedure. The algorithm outputs the best candidate partition over all the rounds. It was shown in12 that the
approximation factor achieved by this partition is O(log2
n). As mentioned in Section 4, a different primal-dual algorithm (with some formal similarity to the above algorithm)
was used4 to improve the algorithm to yield an approximation factor of O(log n). This result was recently matched
in16 by an algorithm that stays within the framework of
the cut-matching game. They also showed that the best
approximation factor that can be obtained within the cut-matching framework is Ω( log n ). Designing a O( log n )
approximation algorithm in the cut-matching framework
remains an intriguing open question.
It is instructive to compare the flow-based algorithm described here to a clustering-based heuristic embodied in the
widely used program METIS. 11 That heuristic proceeds by
collapsing random edges until the resulting graph is quite
small. It finds a good partition in this collapsed graph, and
successively induces it up to the original graph, using local
search. The flow-based algorithm may be viewed as a continuous version of this heuristic since each matching may
be thought of as “virtually collapsing” each matched pair.
In particular, early iterations of the flow-based algorithm
will select matchings that mostly consist of random edges.
Moreover, the cuts provided by the cut player will rarely
partition the resulting connected components. Thus, it
will proceed very much like METIS. Indeed, this algorithm
might have an advantage over METIS since the “virtual collapsing” of edges in the actual sparse cut need not preclude
finding this cut.
We point the reader interested in empirical results to
Chris Walshaw’s graph-partitioning benchmark (http://
staffweb.cms.gre.ac.uk/ c.walshaw/partition/), which provides results of various heuristics on an interesting set
of benchmarks. The impressive results for METIS can be
compared to SDP (by Lang and Rao), which uses a simplified version of SDP with a max-flow cleanup. Though this
resembles the max-flow-based algorithm described in this
section, to our knowledge, the specific algorithms discussed in this paper have yet to be rigorously compared
against METIS.
6. coRRectness PRoof foR the
GeometRic aPPRoach
In this section, we sketch a proof of the main geometric theorem of, 6 for any well-separated set of points on the surface
of the unit sphere in ℜd that satisfy the triangle inequality,
there are two linear-sized almost antipodal sets, S, T, that are
∆ =1/ log n ,separated. The sketch here also incorporates a
simplification due to Lee. 13
Recall that our procedure for identifying these two sets S,
→
T was to project the points on a random line u through the
origin, discard all points whose projection has absolute value
less than 1/ d , and label the remaining points as being in
P and N, according to whether their projection is positive or
negative. We then discarded pairs of points from the two sets
that were less than ∆ separated, to finally obtain sets S and T.
→
For the theorem to fail, for most choices of directions u,
most points must be paired and discarded. Recall that for a
pair to be discarded, the points must be ∆-close to each other
while their projection on u→ must be at least e = 2 s apart.
d
These discarded pairs form a matching for that direction. Let
us make a simplifying assumption that all n points are paired
and discarded in each direction. (In the actual proof, we use
an averaging argument to show that there are Ω(n) points
such that in most directions a constant fraction of them is
matched.)
→
The overall plan is, given a random direction u, to piece
