I'll prove this performance guarantee for you on the next slide.
But let me first make a couple of comments. So first of all, the analysis
of this algorithm stated in the theorem is tight.
The 50% cannot be improved without making additional assumptions about the input.
Indeed, here's an example, which is itself, is even I bipartite graph.
So it's a tractable special case of maximum cut.
But even on bitartike graphs, the local searh heuristic might return to you a cut
which has merely 50% of the edges of a globally optimal, maximum cut.
The example is drawn here in green. There's just 4 verticles and 4 edges.
As I said it is a bi-parted graph, so the best part is to put U and W in one group
and V and X in one group. That cuts all 4 of the edges.
On the other hand, one possible output of the local search algorithm is the cut
where U and V are in 1 of the groups. A, and W and X are the other group B.
So this cut has only 2 crossing edges, only 50% of the maximum possible, yet it
is locally optimal. If you take any of the 4 vertices and you
switch it to the other group, you get a cut with 3 vertices on one side and then
the vertex by itself, since every vertex in this graph has degree 2, all of those
cuts are also only going to have 2 crossing edges.
The second cautionary tale that I need to tell you is that you maybe shouldn't be
super impressed with the perofmance guarnatee of 50% for the maximum cut
problem. Indeed, even if I just took a uniform at
random cuts, by which I mean for each of the invertices I flip Independently a
fair coin. If the coin comes up heads, I put that
vertex in A. If the coin comes up tails, I put that
vertex in B. The expected number of edges that cross a
random cut chosen in this way, is already 50% of the edges of the graph.
Just for kicks, let me sketch a quick proof of this fact.
Some of you may remember from part 1, I introduced a decomposition principle for
analyzing the expected value of complicated random variables.
You have a complicated random variable that you care about, what do you do, you
express it as the sum of indicator random variables.
Random variables that only take on the values of 0 and 1.
When you apply linearity of expectation that reduces computing the complicated
expectation, to a sum of simple expectations.
So it turns out that decomposition principal works beautifully to prove this
fact The complicated random variable that we care about is the number of edges that
cross a random cut. The constituents that are indicator 0 1
random variables are just whether or not a given edge crosses a random cut.
That is for an edge E of this input graph G, I'm going to define the random
variable X of E to be 1 if it's 2N. Points wind up in different groups, and 0
if its 2 end points wind up in the same group.
So what's the expected value of one of these indicator random variables x sub e?
Well, as with any indicator random variable, that's just the probability
that x of e=1, the probability that this edge e is cut by a random cut.
What's the chance of that? Well lets say the endpoints of edge E, are u and v.
There is 4 possibilities; u and v could both be in A, u and v could both be B, u
could be in A and v could be in B, or u could be in B, and v could be in A.
Each of those 4 outcomes is equally likely, probability of 1/4.
In the first 2 cases, this edge is not cut by the random cut, the 2 endpoints
are on the same side. In the other 2 cases, it is cut, they're
on different sides. So it's a 1/2 probability that this edge
is cut in a random cut, therefore the expected value of X sub B is 1/2.
And now we're good to go just by applying linearity of expectations.
So, precisely, what do you care about? We care about the expected number of edges
across a random cut. Well the number of edges crossing a cut
is just by definition the sum of the axes over all of the edges E.
X E is just whether or not. Now the given edge crosses the cut.
So the expected value of the random variable we care about the number of
crossing edges that's by linear [INAUDIBLE] expectation.
Just the sum of the expected values of these indicated random variables the X of
e's. Each of those has value one half, we're
summing up one for each of the edges. So the total of the sum is just the
number of edges divided by 2 and as claimed.
Thanks for indulging my little digression.
Again, the point of which is that just taking a random cut digital performance
guarantee of 50% for the maximum cut problem.
But, in the defense of local search, which also only gets a 50% performance
guarantee, it took a while and in fact you have to work pretty hard to do, to
get a performance guarantee better than 50% with a polynomial time algorithm, for
the max cut problem. The most famous such algorithm is by
Gilmers and Williamson. That took until 1994 and it requires a
tool called semi-definite programming, something that's even more powerful than
linear programming. Let's now prove that local search is
guaranteed to output a cut whose number of crossing edges is at least half.
The total number of edges ion the graph. So pick your favorite locally optimal cut
A-B. And here by locally optimal, I just mean
something that the algorithm might return That is, a cut for which it is impossible
to swap a single vertex from one side to the other and improve the value of Of the
cut. By virtue of being locally optimal it
must be the case that furthest cut AB and for every single vertex of V, the number
of edges incident to this vertex that are crossing the cut is at least as large as
the number of vertices incident to this vertex that do not cross the cut, so the
previous notation that is C sub V. Is at least as big as D sub V.
If not, swapping V would give us a better cut.
So we have N of these inequalities, one is for each vertex V, so we can
legitimately sum up those inequalities combining them into one.
Now, let's focus first on the right hand side of this summed up inequality, so the
sum over all of the vertices in the graph.
Of the number of edges incident to the vertex that are crossing the cut.
Now here's the main point, what is this sum on the right hand side counting? It's
counting each edge that crosses the cut AB exactly twice.
Consider an edge, say U,W which is crossing the cut AB.
It gets counted twice in the right hand side, once when V=U and once when V=W.
We can apply exactly the same reasoning to the left hand side.
What is this I'm counting? It's counting each non-crossing edge exactly once.
Consider an edge against a u comma x who's both endpoints are on the same
side. That's going to be counted once in this
sum when v=u and then again when v=x. Now we want to compare the number of
crossing edges of this locally optimal cut to the total number of edges.
So on the left hand side we're missing the crossing edges, so to complete that
into all of the edges let's just add double the number of crossing edges to
both sides of this inequality. On the left hand side, we get double of
all of the edges and now on the right hand side we have 4 times the number of
crossing edges. Dividing both sides of this inequality by
4, we see we've proved the theorem. The number of edges that cross A,B is
indeed a full 50% or more of the total number of edges in the graph.
It's interesting to discuss briefly how the conclusions we've reached for a local
search for a max cut extended to a natural weighted version of maximum cut.
So which facts about the unweighted special case extended the weighted case
and which facts do not? Well it still makes perfect sense to take a local
search approach to the weighted version of the maximum cut problem.
Now for each vertex in a given cut, you just look at the total weights of the
incident edges that are crossing the cut and the total weights of the incident
edges that are not crossing the cut. And whenever the weights of the edges not
crossing the cut is strictly bigger, that's an opportunity to improve the
current cut, by moving the vertex to the opposite side.
One cool thing is that the performance guarantee that we just established of 50%
for the output of local search, that carries over to the weighted case and the
proof remains essentially the same and I'll leave it for you to check that in
the privacy of your own home. Now, it's also true that in the weighted
case a random cut still gets 50% of the total weight of the graph.
So, perhaps this performance guarantee is not Nothing really to write home about.
What breaks down is the running time analysis.
Remember how this went for the unweighted case.
We argued that there can be at most n choose 2 edges crossing any cut, and
since every iteration of local search increases the number of crossing edges,
it has to halt within a quadratic number of iterations.
And that means it's easy to implement the algorithm.
In polynomial time. One way to think about what's special
about the unweighted version of the maximum cut problem is that even though,
as we've seen, the graph has an exponential number of different cuts, all
of those exponentially many cuts only take on a polynomial number of Different
objective function values. The number of crossing edges is somewhere
between 0, and n choose 2. By contrast, once the edges can just have
any old weights, now, you can have an exponential number of cuts, with an
exponential number, of distinct objective function values, of distinct values for
their total weight. That means, just because your strictly
improving the total weight crossing the cut in each iteration It does not imply
that you're going to converge in a polynomial number of iterations.
And in fact, it's a highly non-trivial exercise to prove that there are
instances of weighted maximum cut, in which local search takes an exponential
number of iterations before converging.