Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.
Given an undirected graph with edge costs and a subset ofk=3 nodes calledterminals, a multiway, ork-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The multiway cut problem is to find a minimum-cost multiway cut. This problem is Max-SNP hard. Recently, Calinescu et al. (Calinescu, G., H. Karloff, Y. Rabani. 2000. An improved approximation algorithm for Multiway Cut.J. Comput. System Sci.60(3) 564--574) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (3/2-1/ k)-approximation algorithm.In this paper, we study their geometric relaxation. In particular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). Fork=3, we show the integrality gap is 12/11, giving tight upper and lower bounds. That is, we exhibit a family of graphs with integrality gaps arbitrarily close to 12/11 and give an algorithm that finds a cut of value 12/11 times the relaxation value. Our lower bound shows that this is the best possible performance guarantee for any algorithm based purely on the value of the relaxation. Our upper bound meets the lower bound and improves the factor of 7/6 shown by Calinescu et al.For allk, we show that there exists a rounding scheme with performance ratio equal to the integrality gap, and we give explicit constructions of polynomial-time rounding schemes that lead to improved upper bounds. Fork=4 and 5, our best upper bounds are based on computer-constructed rounding schemes (with computer proofs of correctness). For generalk we give an algorithm with performance ratio 1.3438-e k .Our results were discovered with the help of computational experiments that we also describe here.
Introduction
As the field of approximation algorithms matures, methodologies
are emerging that apply broadly to many NP-hard
optimization problems. One such approach (e.g., [7,
has been the use of metric and geometric
embeddings in addressing graph optimization problems.
Faced with a discrete graph optimization problem, one
formulates a relaxation that maps each graph node into a
metric or geometric space, which in turn induces lengths
on the graph's edges. One solves this relaxation opti-
mally, and then derives from the relaxed solution a near-optimal
solution to the original problem.
This approach has been applied successfully [2] to
the min-cost multiway cut problem, a natural generalization
of the minimum (s, t)-cut problem to more than two
terminals. An instance consists of a graph with edge-
costs and a set of distinguished nodes (the terminals).
The goal is to find a minimum-cost set of edges whose
removal separates the terminals. If the number of terminals
is k, we call such a set of edges a k-way cut.
The first approximation algorithm for the multiway
cut problem in general graphs was given by Dahlhous,
Johnson, Papadimitriou, Seymour, and Yannakakis [4].
It used a traditional minimum (s, t)-cut algorithm as a
subroutine and had a performance guarantee of 2-2/k.
In the work that prompted ours, Calinescu, Karloff,
and Rabani [2] used a novel geometric relaxation of k-way
cut in a (3/2-1/k)-approximationalgorithm. Their
relaxation uses the k-simplex
which has k vertices; the i th vertex is the
point x in # with x
The relaxation is as follows: map the nodes of the graph
to points in # such that terminal i is mapped to the i th
vertex of #. Each edge is mapped to the straight line between
its endpoints. The goal is to minimize the volume
of G,
vol(G) .
edges e
where |e| denotes the length of the embedded edge e,
defined as half the L 1 distance between its endpoints,
and cost(e) is the cross-sectional area of edge e.
To see that the above is a relaxation of minimum k-way
cut, consider any k-way cut and let S i be the set
of nodes reachable from terminal i in the graph with the
cut-edges removed. Consider a geometric embedding in
which all nodes in S i are mapped to vertex i of #. For
any edge, the distance between its edges is either 0, if
the endpoints lie in the same S i , or 1, if the endpoints lie
in distinct sets S i . Hence the volume of this embedding
equals the cost of the k-way cut.
The algorithm of Calinescu et al. finds a minimum
volume embedding by linear programming. It then uses
a randomized rounding scheme to extract a cut from this
embedding. Ignoring the graph, the scheme chooses
(from a carefully selected distribution) a k-way cut of
the simplex-a partition of the simplex into k subsets,
each containing exactly one vertex of the simplex. The
k-way cut of the simplex naturally induces a k-way cut
in the embedded graph-namely, the set of edges with
endpoints in different blocks of the partition. This cut
has expected cost at most 3/2 - 1/k times the volume
of the embedding.
Our results. Our goal is to further understand the geometric
relaxation, with the hope of developing better
approximation algorithms. We aim to determine the integrality
gap of the relaxation and to find an algorithm
whose approximation ratio matches the integrality gap.
Note the the integrality gap is the best approximation ratio
we can achieve for an algorithm that compares itself
only to the embedding volume.
In this paper, we resolve this question for 3-cut and
provide improved results for the general k-cut problem.
For we give a rounding algorithm with performance
ratio 12/11, improving Calinescu et al.'s bound
of We also show that 12/11 is the best
possible bound, exhibiting a graph with a gap of 12/11
between its embedded volume and minimum 3-way cut.
Thus, for we determine the exact integrality gap
and give an optimal algorithm.
For larger k, we obtain results based on both computation
and analysis. For 4, 5, we use LP-derived and
-analyzed rounding schemes to give bounds of 1.1539
and 1.2161 respectively, improving the corresponding
bounds of Calinescu et al. of 1.25 and 1.3. For larger k
we give a single algorithm obtaining a (analytic) bound
of 1.3438 - # k where # k > 0. The quantity # k can be
evaluated computationally for any fixed k; we use this
to prove that 1.3438 - # k < 3/2 - 1/k for all k.
Our efforts to find geometric cutting schemes that
achieve good guarantees were guided by experiments:
we formulated the problem of determining an optimal
probability distribution on k-way cuts of the simplex as
an infinite-dimensional linear program, and solved discrete
approximations of this linear program and its dual.
From these solutions we were able to deduce the lower
bound and, using that, the upper bound for k = 3. These
experiments also guided our search for cutting schemes
that work for larger values of k.
The upper and lower bounds for discovered
independently by Cunningham and Tang [3].
Presentation overview. In Section 2 we discuss the
geometric ideas underlying the problem. In Section 3
we describe the computational experiments we undertook
and the results it gave for small k. In Sections 4
and 5 we solve the 3-terminal case, giving matching upper
and lower bounds. Finally, in Section 6, we present
our improved algorithm for general k.
2 The geometric problem
Finding the integrality gap of and a rounding scheme for
the relaxation turns out to be expressible as a geometric
question. That is, we can express integrality gaps and
algorithmic performance purely in terms of the simplex,
without considering particular graphs or embeddings.
2.1 Density
Recall that a k-way cut of the simplex is a partition of
the simplex into k subsets, each containing a unique vertex
of the simplex, and that such a cut induces a k-way
cut of any embedded graph. By a cutting scheme, we
mean a probability distribution P on k-way cuts of the
simplex. For any line segment e, the density of P on
segment e, denoted # k (P, e), is the expected number of
times a random cut from P cuts e, divided by the length 1
|e| of e. Define the maximum density of P , # k (P ) and
the minimal maximum density #
k as follows:
e
It is easy to see that the maximum density line segment
will in fact be an edge of infinitesimal length, since any
segment can be divided into two edges, one of which
has density no less than the original. Thus, in the remainder
of this paper, we will focus discussion on such
infinitesimal segments.
The relevance of #
k is the following (this is implicit
in the work of Calinescu et al.):
Lemma 2.1 For any cutting scheme P and embedded
graph G, the expected cost of the k-way cut of G induced
by a random k-way cut from P is at most # k (P ) times
the cost of the embedding of G.
1 By analogy to the length of an edge, the length of a segment is
defined as half the L 1 distance between its endpoints.
Corollary 2.2 Any cutting scheme P yields an approximation
algorithm with approximation ratio at most # k (P ).
Proof Sketch: The endpoints of any edge e are embedded
at two points in the simplex, so the edge corresponds
to a segment connecting those two points. The
expected number of times the edge is cut is # k (P, e) - |e|.
By the Markov inequality this upper bounds the probability
that the edge is cut. Thus, the expected cost of
the k-way cut is at most
In fact, one can show that #
k is both the integrality
gap of the geometric relaxation and the best performance
guarantee obtainable by any cutting scheme.
That is, there is an embedded graph whose volume is arbitrarily
close to #
k times its minimum k-way cut and
there is a cutting scheme with maximal density (and
therefore performance guarantee) arbitrarily close to #
k .
This is a consequence of Yao's principle (i.e. von Neu-
mann's min-max theorem, or equivalently strong linear
programming duality, applied in the context of complexity
theory). It also follows that a cutting scheme with
optimum integrality gap can be defined obliviously, independent
of the input graph.
Calinescu et al.'s algorithm gives a cutting scheme
showing that #
1/k. In this paper we show
that #
2.2 Alignment
We have just argued that the key question to study is the
maximum density of line segments relative to a cutting
scheme. Calinescu et al. showed that one can restrict
attention to segments in certain orientations. We say a
segment e in # is i, j-aligned if e is parallel to the edge
connecting vertices i and j of #. We say it is aligned
if it is i, j-aligned for some pair of vertices. Calinescu
et al. observed that since length is proportional to the
and since the aligned edges are the geodesics
of the norm, the endpoints of any segment e can be
connected by a piecewise linear path of total length |e|
whose segments are aligned. The segment e is cut iff
some edge on this path is cut. Given any embedding of
a graph, Calinescu et al. apply this transformation separately
to each segment connecting two embedded ver-
tices, without changing the volume of the embedding.
Thus, without loss of generality one may restrict attention
to embeddings in which all edges are aligned.
Fact 2.3 Segment
2.3 Side parallel cuts (SPARCS)
In this paper, we mainly restrict attention to a particular
set of cutting schemes. Define # x i =#
that # x i =# is a hyperplane that runs parallel to the face
opposite terminal i and is at distance # from that face; it
divides the simplex into two parts, of which # x i # is the
"corner" containing terminal i. An i, j-aligned segment
(x, y) is cut by the hyperplane # x # iff # {i, j} and
# is between x # and y # .
We define a side-parallel cut (sparc) of the simplex:
1. Choose a permutation # of the vertices;
2. For each vertex i in order by # (except possibly the
last), choose some # i # [0, 1];
3. Assign to vertex i all points of # x i # not already
assigned to a previous terminal. We say terminal
captures all these points, and that terminal i cuts an
edge e if it captures some but not all of e.
Thus we are slicing up the simplex using hyperplanes
. In this context, we call each # x i =# a slice.
We consider algorithms that sample randomly from
some probability distribution over sparcs. Our restriction
to sparcs was motivated by several factors. The
rounding algorithm of Calinescu et al. uses only sparcs.
Furthermore, our computational study of the 3-terminal
problem (discussed below) and some related analytic
work gave some evidence that the optimal algorithm was
a distribution over sparcs. Lastly, sparcs have concise
descriptions (as a sequence of k - 1 slicing distances)
that made them easy to work with computationally and
analytically. It is conceivable, though, that one might do
better with cuts that are not sparcs.
Our key idea is expressed in the following fact. For
segment e, let e # be the interval {x # |x # e} and let
min e # denote the smaller endpoint of this interval.
Fact 2.4 An i, j-aligned segment e is cut by a sparc if
and only if it is cut by terminal i or j. Furthermore, for
# {i, j}, the followingconditions are all necessary for
segment e to be cut by terminal #:
(2) For all terminals h preceding # h > min e h .
(3) Terminal # is not last in the order
For probability distributions P on sparcs, one can
obtain bounds on # k (P, e) by using Conditions 1-3 above.
For example, we can restrict our attention to Condition 1:
are uniformly distributed, Condition 1 holds
for terminal i with probability |e| and independently for
terminal j with probability |e|. Thus, the expected number
of times e is cut is at most 2|e|.
Next, consider adding Condition 3. Suppose that
the ordering of terminals is random, meaning that i is
last with probability 1/k. The probability that e is cut
by
Thus, uniformly random # 's and a random ordering
gives a performance guarantee of of 2 - 2/k, matching
the bound of Dahlhous et al. [4].
To improve these bounds, one must use Condition 2.
Calinescu et al. choose a sparc by selecting # uniformly
at random in [0, 1], setting # for each terminal
#, and slicing off terminals in random order. A naive
analysis again derives a density bound of 2 for any i, j-
aligned segment e, with a contribution of 1 from the i
and j slices. Calinescu et al. improve this analysis as
follows. Suppose that the edge is farther from j than
from i. Suppose that # is such that j appears to cut e.
Then if i (which is closer to e) precedes j in the random
slice ordering (probability 1/2), i will capture all
of e and prevent j from cutting it. This reduces the density
contribution of terminal j to 1/2, and leads to their
To improve on the 3/2 bound, we made stronger use
of Condition 2. The analysis of Calinescu et al. only
considers that a segment may be captured by the two
terminals with which it is aligned. We derive stronger
results by observing that other terminals may capture
the edge as well. To do so, we had to change the cut
distribution as well as the analysis. It can be shown that
no distribution that holds all # i equal can do better in
the limit than 3/2 of Calinescu et al. But their idea of
making the # i into dependent random variables is useful.
We explore other schemes based on dependent distribu-
tions. One such scheme for 3-way cut gives us a bound
of 12/11, which is optimal over all schemes for 3-way
cut. Another scheme gives us a bound of 1.3438 that
holds for any number k of terminals. This latter scheme
is designed for large k.
2.4 Additional Observations
We now mention some additional observations whose
full proofs must await the full paper.
What is the best embedding? Perhaps the first
natural question to ask is whether the embedding chosen
by Calinescu et al. is the best possible.
Lemma 2.5 Among all embeddings in the simplex that
minimize some norm (without adding other constraints)
the L 1 norm has the smallest possible integrality gap.
Space limitations require that we omit the (straightfor-
ward) proof of this lemma, which basically relies on
breaking any segment into aligned segments and translating
them and scaling them to the simplex sides.
Symmetry. A second observation is that there is no
benefit in trying to identify a "good terminal order" in
which to cut up the simplex.
Lemma 2.6 There is an optimum sparc cutting scheme
of the following form:
1. choose slice distances (d 1 , . , d k-1 )
2. apply the slice distances (in order) to a uniform
random permutation of the terminals
An analogous "order independence" statement holds for
the best possible (possibly non-sparc) algorithm.
Proof: Consider a best sparc with integrality gap #.
Consider any input embedding. We can "symmetrize"
the embedding, without changing its volume, by averaging
it over all permutations of the coordinates. Our
sparc achieves integrality gap # on the symmetrized em-
bedding. Since the embedding is symmetric, the order
in which the sparc slices terminals is irrelevant. So we
can assume it is some fixed order.
Note, however, that cut value achieved on the symmetrized
graph but slicing in some fixed order is just the
expected cut value achieved by applying the same slices
to the original embedding under a random ordering of
the terminals.
The above lemma shows that there is no worst-case
benefit to considering specific terminal ordering. The
duality argument of Section 2.1 carries over to show that
a sparc with optimum expected integrality gap can be
specified simply as a distribution over slicing distances,
without reference to an input graph embedding.
3 Our Computational Study
In this section we describe some computational experiments
we carried out to help us understand the behavior
of the geometric embedding. One need read this section
in order to understand the following ones.
As discussed above, our goal was to find a distribution
over cuts of the k-simplex that minimized the density
of any segment in the simplex. This problem can
be formulated as an infinite dimensional linear program,
with one variable per cut of the simplex, corresponding
to the probability that that cut is chosen, and one constraint
for every (aligned, infinitesimally small) line segment
inside the simplex, which measures the expected
number of times the chosen cut will cut that segment. Of
course, it is not tractable to solve the infinite LP compu-
tationally, but we expected that discretized versions of it
would be informative.
We applied this approach in two distinct ways. For
the 3-terminal case, we devised an LP that exploited
the planarity of the 3-terminal relaxation, and used it
to home in on the optimal solution, which we then analytically
proved to be optimal. For the general case,
we devised an LP whose solutions are (provable) upper
bounds on the performance of certain rounding al-
gorithms. We solved this LP for small numbers of terminals
(3-9), deriving algorithms with (computer aided)
proofs of the best known performance ratios for these
problems. The solution suggested certain properties that
appear to hold in the "optimal" rounding scheme; we
used these suggestions in our development of (analytic)
solutions for arbitrary numbers of terminals.
3.1 The three-terminal case
For the 3-terminal problem we exploited planarity. The
3-simplex can be viewed as a triangle in the plane. We
discretized the linear program by defining a triangular
mesh over the simplex and considering only edges of
the mesh instead of all line segments in the simplex.
To approximate the best cutting scheme, we computed
the best distribution over 3-way cuts of the mesh.
We used the planarity of the 3-simplex to simplify our
LP formulation. Any 3-way cut of the mesh corresponds
to a collection of paths (representing the boundary of
the cut) through the planar dual of the mesh. Thus the
distribution of cuts corresponds to a packing of these
paths, which can be seen as a kind of flow. So instead
of enumerating all possible cuts, we could define a linear
program that assigned a (multicommodity) flow to
each edge of the dual mesh. This gave us a tractable
representation of the linear program.
We also found it helpful to solve the dual of our
flow-based linear program, which assigns weights to the
mesh edges to minimize the total weight such that every
3-cut has value at least 1. Since each 3-cut corresponds
to a set of two or three paths in the planar dual of the
mesh, the latter constraint can be represented efficiently
by constraining shortest-path lengths (as a function of
the variable edge lengths) in the planar dual. A solution
to the dual can be interpreted as an embedded graph
demonstrating the integrality gap. The dual showed us
the important idea of "ball cuts" versus "corner cuts"
which we will discuss in the following sections, and thus
led to the discovery of the optimum cutting scheme for
three terminals.
3.2 The general case
In the general case, the lack of a planar embedding prevented
us from exploiting nice properties of its cuts; we
were faced with the problem of enumerating cuts as well
as edges. Based on the work of Calinescu et al. and
our own results for the optimal 3-terminal solution, we
decided to limit our exploration to sparcs as discussed
above.
There is still an infinite space of possible sparcs, so
we discretized our problem. Fix an integer grid size N .
A discrete sparc is described by a vector (q 1 , . , q k-1 )
where each q i is an integer in the range [0, N-1]. Given
such a vector, we choose a random sparc by setting d i
uniformly in the range [q i /N, This defines
a probability distribution on (continuous) sparcs. We
now define a linear program to search for a probability
distribution over discrete sparcs (which induces a probability
distribution over continuous sparcs). We define a
variable for each discrete sparc, which reflects the probability
of choosing that discrete sparc, and provide constraints
that aim to minimize the density of any segment
under the probability distribution.
There still appear to be infinitely many constraints
(segments) but we reduce this to a finite number as fol-
lows. The slices at distances q/N for each terminal that
determine our sparc distribution partition the simplex
into cells. For a given distribution on the discrete sparcs,
we can compute a (linear) upper bound on the density
induced on any segment with a given alignment within
a cell, and specify one constraint saying that this upper
bound should be small. Since the cells are small, we expect
all segments with a given alignment to have roughly
the same density under our cutting scheme, so we hope
that the upper bound is reasonable tight. With this sim-
plification, the number of constraints is bounded by the
number of cells times the number of segment alignments
per cell, which is at most k 2 N k .
We determine the upper bound for a cell as follows.
For any discrete cut, the slices generated from it will fall
into one of three categories. If the i th coordinate of the
discrete cut is different from that of the cell, then the
th slice will not pass through that cell: depending on
whether the coordinate is larger or smaller it will either
capture the entire cell or none of the cell. If the i th coordinates
are the same, then the slice might pass through
the cell; we can use that the slice is uniformly distributed
over a range to determine its density contribution.
If we consider an i, j-aligned segment, it can only be
cut if the slices for terminal i or j go through its cell. If
only one of the two slices goes through the terminal then
its contribution to a segment's density is at most 1/N .
If both slices go through the cell, their contribution is at
most 2/N . We ignore the fact that different slices within
the cell might capture the segment before it can be cut,
thus introducing some slack in our upper bound.
We can exploit symmetry to further reduce the number
of constraints we consider. Since by assumption our
sparc slices terminals in random order, two segments
that are identical under permutation of coordinates will
have the same densities, so we need consider only one
of them. Thus, we restrict our constraints to 1, 2-aligned
segments in which the remaining coordinates are in non-decreasing
order.
s
a b
c d
r
s
r
\Omega \Omega Figure 1: This figure illustrates the cuts used for the case 3. The leftmost diagram shows how r might be chosen
for the ball cut. The middle diagram shows one possible resulting ball cut (in bold). The rightmost diagram shows a
corner cut (in bold).
3.3 LP Results
Exploiting symmetry as discussed above, we were able
to solve relatively fine discretizations of the problem.
We wrote a simple program to generate the linear programs
automatically, and used CPLEX to solve them.
While it is difficult to "prove" programs correct, our
computations did converge to the correct 12/11 approximation
ratio for the 3-terminal case.
We give our results below in tabular form. We derived
improved bounds for 4-9 terminals. Note that (un-
der the assumption that the programs were correct) these
are provable upper bounds. In fact, since the programs
output a particular distribution over discrete cuts, their
performance ratio could be proven analytically via a tedious
case analysis (which we have not performed).
k Grid LP Gap 3/2 - 1/k corner cut probability
Our experiments also revealed one interesting fact:
in all cases, the optimum cut distribution made use of
"corner cuts." That is, the output distribution had the following
form: with some probability, place each slice at
a distance chosen uniformly between 0 and 1/3 from its
otherwise, use a (joint) distribution that places
every slice at distance greater than 1/3 from its terminal.
Adding constraints that forced the corner cuts to operate
over a range other than 1/3 of the way from the terminals
worsened the computed performance ratio, hinting
that perhaps the optimal algorithm uses corners of
size exactly 1/3. This result is consistent with the optimal
3-terminal algorithm, however it could be a misleading
artifact of working with a discretized problem.
4 Upper Bound for
Our analytic upper bound of 12/11 for
from a new cutting scheme that we call the ball/corner
scheme. Though for simplicity we present a non-sparc
scheme, there is a similar scheme using sparcs that achieves
the same bound.
For 3, the simplex # can be viewed as a triangle
in the plane, which simplifies our pictures. However,
we continue to use the original three-dimensional coordinate
system to locate points in the simplex. Our cut of
the simplex is determined by some lines and rays drawn
through the triangle; we refer to them as boundaries. We
will show that no segment has high density with respect
to our random choice of boundaries.
As illustrated in Figure 1, denote the vertices of the
simplex 1, 2, 3. Let points a, b, . , f divide the edges in
thirds, so that a-b-f -d-c-e-a is the hexagon in # with
side length 1/3. Note that the hexagon is (a scaled version
of) the unit ball for our distance metric. The points
on the boundary of the hexagon are each at distance 1/3
from the hexagon's center. 2
The ball/corner scheme chooses a ball cut with probability
8/11, otherwise it chooses a corner cut. These
two types of cuts are defined next. The scheme is illustrated
in Figure 1.
Ball cut: Choose a point r uniformly at random from either
line a-c or line b-d. Consider the three lines # x i =r i
parallel to the triangle's sides and passing
through the point r. Each such line is divided at the
point r into two rays. Thus we get six rays. Each side of
the triangle intersects two of these rays. For each side,
randomly choose of the two rays that hit it. This gives
three rays; they form the boundary of the 3-way cut.
Corner Cut: Choose two terminals in {1, 2, 3}, and a
value # [2/3, 1], uniformly at random. For each of
the two chosen terminals i, let l . The two
lines l i form the boundaries of the 3-way cut.
Remember that we measure length as half the L 1 norm.

Figure

2: The lower bound for 7). The paths from 2 to 3 are on the left. The entire graph is on the
right. On the border, overlapping paths are drawn side-by-side for clarity, so line width represents edge cost.
Analysis. We first state two simple properties of the
ball cut that we need to analyze the performance of the
cutting scheme:
Fact 4.1 Each of the 3 coordinates of the random point
r is uniformly distributed in [0, 2/3].
Fact 4.2 Once r is chosen, each one of the six candidate
connecting r to one side of the triangle is chosen
with probability 1/2.
Theorem 4.3 The maximum density of the ball/corner
scheme is 12/11, so #
Proof: We show that the expected density of any segment
e is at most |e| - 12/11. For the ball cuts, we use
only the two facts claimed above. Since these two facts,
as well as the corner cut scheme, are symmetric with
respect to the three coordinates, it suffices to prove the
claim only for a 1, 2-aligned segment e. We will consider
several cases, depending on where e is located.
First, assume e is located entirely in the hex. Such a
segment cannot be cut by a corner cut, so we need only
consider the density when a ball cut is made and multiply
by the probability of choosing a ball cut, namely
8/11. Assume a ball cut is made. Then e can only be
cut by rays of in # x i =r i for 2. By Fact 4.1, r i
is uniformly distributed in [0, 2/3]. Hence, the probability
that # x i =r i goes through e is |e|/(2/3) since e is
e, it is at a single point.
By Fact 4.2, the ray of # x i =r i containing this point is
picked for the cut with probability 1/2. Thus the expected
number of times e is cut is 8
Exactly the same argument applies if the edge is in
the corner closest to terminal 3. The ball cut contributes
the same 12/11 density, while the corner cut contributes
nothing (note that a 1, 2-aligned edge is parallel to the
line # x3=r i
, so cannot be cut by it).
Second, suppose segment e is in the corner closest
to terminal 1 (a symmetric argument applies if e is in
the corner closest to terminal 2). In this case, if a ball
cut is made, the above analysis applies except that only
the line # x2=r2 can cut e (the line # x1=r1 never enters
the corner), so the density contribution of the ball cut is
halved to |e| 6
11 . But the edge can also be cut by a corner
cut. A corner cut is chosen with probability 3/11. When
it is, two of the three terminals are chosen, so terminal 1
is chosen with probability 2/3. If terminal 1 is chosen,
then, since the cutting line near terminal 1 is of the form
# x1=1-p , where p is chosen uniformly in [0, 1/3], the
probability that the line cuts e is |e|/(1/3). Thus, the
expected number of times that the edge e is cut (by a
ball cut or corner cut) is |e| 6+ 3
11 .
Finally, if e spans several regions (e.g. it lies in a
corner and in the hex), e can be partitioned into sub-segments
each contained entirely in one region, and the
previous analysis applied to the sub-segments.
5 Lower Bound for
Theorem 5.1 For the minimum maximum density
Hence, the integrality gap for the geometric
relaxation is 12/11.
Note that this theorem applies to all cutting schemes, not
just sparcs.
Proof: Fix N to be any positive integer. We construct
an embedded weighted graph GN with no 3-way cut of
cost less than 12N - 3, but with an embedding of cost
11N +3. This implies that no cutting scheme has maximum
density less than (12N-3)/(11N+3), because by
Lemma 2.1 such a cutting scheme applied to GN would
yield a 3-way cut with expected cost less than 12N - 3,
a contradiction. Since N is arbitrary, the result follows.
Our construction (for shown in Figure 4.
For any pair of distinct terminals i, j and number
d # [0, 1], define embedded path p(i, j, d) as follows.
Let # be the terminal in {1, 2, 3} - {i, j}; let a be the
point on segment i# at distance d from i; let b be the
point on segment j# at distance d from j. Then p(i, j, d)
is the union of the three segments ia, ab, and bj.
We form the graph from 9N paths p(i, j, d) for 0 #
d # 2/3; where d is an integer multiple of 1/(3N ).
Although we describe the graph as a set of paths, technically
it is a planar graph consisting of nodes and edges
as follows: for every point in # whose coordinates are
integer multiples of 1/(3N ), there is a node in the graph
embedded at that point; for every pair of nodes embedded
has an edge with cost equal
to the number of paths that pass through both nodes.
With this understanding, we now specify the graph.
For each of the 3 distinct pair of terminals i, j, there
are 3N paths. Of these paths, N run directly between
the terminals; that is, there are N copies of p(i, j, 0).
The remaining 2N paths are the paths p(i, j, m/(3N
The total cost of the embedding is the total length
of the paths. Since a path p(i, j, m/(3N )) has length
calculation shows that the total
length of the paths is 11N/3 + 1.
Next we lower bound the cost of any 3-way cut.
Since the graph is planar, any minimal 3-way cut corresponds
either to a disconnected cut (meaning that the
cut is the union of two disjoint 2-way cuts, each separating
some terminal from both other terminals), like our
upper bound's corner cut, or a connected cut (meaning
that the cut edges give, in the planar dual, three paths
connected at some central node and going to the three
sides of the triangle), like our upper bound's ball cut.
Any 3-way cut must cut all of the 9N paths at least
once. To finish the proof, we will argue that for either
type of 3-way cut (connected or not), at least 3N - 3
paths are cut twice, so that the edges cut by the 3-way
cut cost at least 12N - 3. This is easy to verify for a
disconnected cut: a disconnected cut is the union of two
2-way cuts, so the 3N paths running between the two
terminals that are cut off must be cut twice.
Now consider any connected cut. In the planar dual
of GN , the connected cut corresponds to a central node
and three paths from the node to each side of the trian-
gle. Let point inside the face of
GN corresponding to the central node. Consider a path
p(i, j, d) such that d # x # , where #= i, j. That is, X
is inside the cycle formed by the union of p(i, j, d) and
p(i, j, 0). Then the path p(i, j, d) is cut twice by the connected
cut. For fixed i and j, the number of such paths
(with d # x # ) is at least (2/3 - x # )N/3 - 1. Thus, the
total number of such paths is at least (2/3
6 Improvement for general k
Theorem 6.1 For all k, #
1.3438. Moreover, there
is a k-way cut approximation algorithm with an approximation
guarantee of 1.3438.
Our bound improves on the Calinescu et. al. bound of
14. For 3 < k < 14, we can
also obtain improvements by taking advantage of k being
small (see Section 6.1).
As discussed in Section 2.3, the essential observation
in this analysis is that many slices can capture an
edge before it has a chance to be cut.
We will use a (sparc) cutting scheme called ICUT:
we choose k slicing thresholds # i , and apply the slices
to a random permutation # of the terminals.
To bound the cutting density of our scheme, we will
bound the density of every segment. As justified in Section
2.2, we consider a segment of length # > 0, and let
# approach zero. As in the ball/corner scheme, by symmetry
we can assume without loss of generality that the
segment is 1, 2-aligned.
to be the density which which
ICUT cuts a 1, 2-aligned segment of infinitesimal length
located at x 1 , x 2 , . , x k . We will show:
Theorem 6.2
11/12 otherwise.
The final cutting scheme chooses to ICUT with probability
chooses a corner cut.
The corner cut is chosen by the natural generalization of
the scheme for 3: choose a value # [6/11, 1].
The k-cut consists of the hyperplanes l
each i. Note that the last corner cut need not technically
be made but it simplifies the analysis.
This combined scheme gives a maximum density
of max{(2.012096)#, (11/12) #+ (11/5)(1 - #
1.3438, proving Theorem 6.1. It remains to prove Theorem
6.2.
The cumulative probability distribution function for
any # i is is F 1}. The corresponding
probability density function is
Consider a 1, 2-aligned segment of length # with one
endpoint fixed at x 1 , x 2 , . , x k . As # goes to zero, the
density of this segment goes to
where the sum is over all k! orderings of the terminals.
This formula is true for any F and accounts for the probability
of the 1, 2-aligned edge being captured by the terminals
that go before 1 or 2. This savings is the key to
improving on the factor of 3/2 for large k.
Note that d k
(provided
cannot save the edge. Note also that d k is symmetric
with respect to the variables x i for i > 2. Define
x3 ,.,x k
In these definitions, is required to lie in
the k-simplex.
D k is the maximum density of any 1, 2-aligned infinitesimal
segment with an endpoint whose first two co-ordinates
are x 1 , x 2 . Note that the maximum is well-defined
and achieved by some x 3 , . , x k because the
simplex is closed under limit.
To understand ICUT, our first goal is to characterize
D k . We consider C k as it is one candidate for D k .
Lemma 6.3 D k
Thus the D k are a nondecreasing sequence bounded
from above (by 2). This implies that D# is well-defined.
We will see later that C# is also well-defined.
Next we show that for fixed x 1 and x 2 , the worst
case occurs at either the "central point" x 1 , x
or the "three-terminal" point
(Analogous results hold for any convex or concave F .)
Lemma 6.4
Proof: Fix x 1 and x 2 . Let
1: Among all x 3 , . , x k such that 0 # x
6/11 for all i > 2 (and x 1 , x 2 , . , x k is in the simplex),
the unique maximizer of d k
Suppose for contradiction that
some other such x 3 , x 4 , . , x k maximizes d k . Then
2. Considered just as a function
of x i and x j (holding the other coordinates fixed)
where p, q, r and s are nonnegative and independent of
x i and x j . Furthermore
in x i and x j . Consider increasing x i and decreasing x j
at equal rates. This maintains
increases d k at a rate proportional to
This is positive because F #
and F
contradicts the choice of x 3 , . , x k .
2: Among all x 3 , . , x k such that x i # 6/11
for some i > 2 (and x 1 , . , x k is in the simplex), the
unique maximizer of d k
contradiction
that some other such x 3 , x 4 , . , x k maximizes
d k . Fix some j > 2 such that 0 < x j < 6/11 #
the expression (2) reduces to
If we increase x i and decrease x j at
the same rate, the rate of increase in d k is qF #
contradicting the choice of x 3 , . , x 4 .
The two claims together prove the lemma.
Lemma 6.5 For k # 4, C k
Here 2). The last inequality
follows from Lemma 6.4 (using c # 1/2 < 6/11).
An immediate corollary is that C# well-defined
and C k Using
this and Lemma 6.4, to bound D# it suffices to bound
C 3 and C# . We begin with C# .
Lemma 6.6
11/12 otherwise.
Proof: Fix x 1 and x 2 . Our first goal is to derive a
closed-form expression for C k k. Fix k
for now and let x
2.
For the probability that the
segment at captured by a terminal
other than j before the jth cut is made:
We will derive a closed-form expression for S 1 (and
by symmetry for S 2 ). Recall that x 2. We
thus rewrite
Here we condition on q, the number of j such that #(j) <
#(1). Note that q is uniform in [0, k - 1] while q
k-1 is
the probability that #(2) < #(1), given q.
A change of variables and rewriting give
Now we let k #. The two sums above have
standard closed forms that tend respectively to
where a .
Of course S 2 is the above with x 1 replacing x 2 . This
gives us our closed-form expression for C#
a
a 2
where
The above equality holds for any F . Using this closed
form and our particular choice of F , we now show the
two desired bounds on C# .
Case 1: x 1 , x 2 # 6/11. In this case a = 11/6(1 -
a
a
a 2
where
In the rest of this case (Case 1),
we will prove that C(a) # 2.012096 for a # (0, 11/6).
The cases by the continuity
of C. The claim is "obvious" from a plot but the
somewhat technical proof appears below.
We show that C(a) is strictly concave for a # (0, 11/6).
It therefore has a unique maximum at some a 0 , where
and C # (.295) # -0.00009 < 0, so a 0 # (.294, .295).
Hence
To show C(a) is strictly concave, we show that C # (a) is
strictly negative. Now, C # (a) = 117 e -a a 2
a 3 +36
6 e -a a 3 +22-22 e -a
a 3 and C #
- 36 a -
To show that C # (a) is negative, it suffices to prove
that
is negative. By substitution,
0, so it suffices to show that D # has only one zero a 1 ,
D # (a) < 0 for a < a 1 and D # (a) > 0 for a > a 1 . Here
and D # (a) 33). For a #
(0, 11/6], D # has only one zero a
and D # (a) < 0 for a < a 2 and D # (a) > 0 for a > a 2 .
That is, D # is first decreasing and then increasing. Since
D # has only one zero a 1 for a # (0, 11/6].
Case 2: x 1 or x 2 # 6/11. Assume x 1 # 6/11 (the
case x 2 # 6/11 is symmetric). In this case, F #
and F
a -6
a 2 .
As before, let We will prove that
C(a) # 11/12 for a # [0, 11/6]. First, lim a#0
11/12, so C(a) # 11/12 follows if we can show that
We have
for a > 0, C(a) # 0 if and only if E(a) # 0. Since
a # (0, 11/6]. We have
that
a # (0, 11/6]. We have
We conclude that C#
Lemmas 6.4 through 6.6 prove that, for x such that
11/12 otherwise.
The remaining case is when x 2.
In this case by Lemma 6.4,
and 5/11. Thus, to finish the proof of the
theorem, it suffices to show the following lemma.
Lemma 6.7 If x 1
Proof: Let x
By inspection of (1), C 3
This proves Theorem 6.2.
6.1 Improvements for small values of k
For particular values of k it is possible to refine the analysis
in the proof of Theorem 6.1 to get improved bounds.
In this case it is useful to modify the algorithm so that it
only uses k - 1 cuts instead of k. In particular, we do
not use the cut for the terminal j with k. The
analysis for this case goes similarly, with our definitions
appropriately modified to reflect that we are using k - 1
instead of k cuts.
Then, instead of passing to the limit, C k
be evaluated directly. Following this approach we obtained
the following performance guarantees for particular
k:
6 0.576 0.659 1.244
9 0.557 0.659 1.277
Here, "corner" is the placement of the corner (anal-
ogous to 6/11), p is the probability of choosing ICUT,
and "ratio" is an upper bound on the resulting ratio. The
corner sizes and p's are approximate and only close to
optimal and the ratios were evaluated numerically without
formal verification.



--R

An O(log theorem and approximation algorithm
"An improved approximation algorithm for MULTIWAY CUT"
"Optimal 3-terminal cuts and linear programming,"
The complexity of multiterminal cuts.
Joseph (Seffi) Naor
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.
An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms
The geometry of graphs and some of its algorithmic applica- tions
--TR

--CTR
Chandra Chekuri , Anupam Gupta , Amit Kumar, On a bidirected relaxation for the MULTIWAY CUT problem, Discrete Applied Mathematics, v.150 n.1, p.67-79, 1 September 2005
Adi Avidor , Michael Langberg, The multi-multiway cut problem, Theoretical Computer Science, v.377 n.1-3, p.35-42, May, 2007
Steve Hanneke, An analysis of graph cut size for transductive learning, Proceedings of the 23rd international conference on Machine learning, p.393-399, June 25-29, 2006, Pittsburgh, Pennsylvania
multiway cut;approximation algorithm