Definition

Loading...

Do curso por École normale supérieure

Approximation Algorithms Part II

40 ratings

École normale supérieure

Approximation Algorithms Part II

40 ratings

Approximation algorithms, Part 2 This is the continuation of Approximation algorithms, Part 1. Here you will learn linear programming duality applied to the design of some approximation algorithms, and semidefinite programming applied to Maxcut. By taking the two parts of this course, you will be exposed to a range of problems at the foundations of theoretical computer science, and to powerful design and analysis techniques. Upon completion, you will be able to recognize, when faced with a new combinatorial optimization problem, whether it is close to one of a few known basic problems, and will be able to design linear programming relaxations and use randomized rounding to attempt to solve your own problem. The course content and in particular the homework is of a theoretical nature without any programming assignments. This is the second of a two-part course on Approximation Algorithms.

Na lição

Maximum Cut and Semi-Definite Programming

We introduce a generalization of linear programming, semi-definite programming.This module uses semi-definite programming to design an approximation algorithm for another basic problem, the maximum cut problem.

Conheça os instrutores

Claire Mathieu

[MUSIC]

In this chapter we will study the famous Maxcut problem and

present the famous algorithm due to Michelle Gomez and

David Williamson from the mid-1990s.

Perhaps the most famous approximation algorithm that there is.

Okay, so let's talk about the Maxcut problem.

What is the definition of this problem?

Given, a graph, with non-negative edge weights.

A graph with edge weights,

find a partition of the vertices into two subsets.

So as to maximize the weight of the edges going across the cut.

The total weight of the edges going from the left to the right side,

that's the Maxcut problem.

Where does it come from?

It comes from, for example, it's relevant to statistical physics.

And it also has many variants that come up in applications.

Let's look at this on some example, simple example.

Take the grid, the four-by-four grid, 16 vertices.

Imagine every edge has weight equal to 1.

What is the value of Maxcut?

We have to try every cut to see what the maximum is,

that's the naive way of doing it.

Let's see, let's take this cut, separating this vertex from everything else.

This cut crosses two edges, value 2.

Let's take a different cut.

The vertical cut separating the left side vertices from the right side vertices.

Value one, two, three, four edges across.

Four edges go across the cut, the value of this cut is 4,

it is better than the previous one.

How about the partition into empty set on one side and

the entire set on the other side?

No edge crosses, value zero.

How about this cut?

This red cut here, I'm not going to trace it because it's too hard.

But you can check that it crosses every single edge.

Every single edge is crossed.

And therefore, Its value is 24.

All the edges are cut by this partition.

And that is the best possible.

In this case, the graph is barred by tight, that helps.

So, let's see,

here are some properties that are not imposed in the definition of Maxcut.

There is no particular pair {s,t} of vertices

that must be separated by the cut.

And the cut does not have to be 50-50.

It does not have to be a balanced cut.

If you look at this,

about two-thirds of the graph is on the left and the one-third is on the right.

That is allowed.

No constraint on the cardinalities of the sides,

no constraint on where specific vertices go.

It's just any cut among the two to the end possible cuts.

For each cut, look at the weight of edges crossing, take the maximum.

That's the Maxcut problem.

Probably, it reminds you of something you have seen

earlier in some algorithms cross Mincut.

Let's take a quick look at the similarities and differences between them.

In both cases we're given a graph with non-negative edge weights.

In addition, for Mincut we have two special vertices, s and t.

That's what sometimes causes the confusion.

In both cases, the goal is to find a partition of the vertices into two sets.

But in addition, in the case of Mincut, we want to separate s from t.

In case of Maxcut, we want to maximum the weight of the edges across the cut.

In the case of Mincut, we want to minimize the weight of edges across the cut.

You can see here, this cut separates s from t,

and it has very few edges crossing and they are very light compared to that cut.

Well what's interesting is that the Mincut problem can be solved in polynomial time.

It's related to the max flow problem, but

the Maxcut problem is NP-hard.

Who proved it's NP-hard?

Take a guess.

Karp, of course, of course.

He's the one who took these initial fundamental problems and

proved them all NP-hard.

So, we have our basic fundamental problem from graph theory, graph optimization.

We know it's NP-hard, and

now we want to try to design an approximation algorithm for it.

And this will lead us to a new technique for

the design of algorithms in approximation.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play