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.
A rounding algorithm
Loading...
From the course by École normale supérieure
Approximation Algorithms Part II
40 оценки
From the lesson
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.
Meet the Instructors
Claire Mathieu
[MUSIC]
In this section, I will show how to round the solution of a quadratic program.
So we have our quadratic relaxation for
Maxcut where every vertex has an associated unit length vector.
And we have solved it using a mysterious black box algorithm called
the ellipsoid algorithm.
Now we have our vectors, we need to figure out how to deduce
a partition of the vertices of the graph into two parts,
that is given the vector Vi, a unit vector.
We want to deduce the value of Xi of among two possibilities, and
here it is easier to think of the two possibilities as being -1 or 1.
So we have a vector on the sphere in high dimension, and
we want to decide whether to associate to it the value -1 or the value 1.
Once we have done that, as a result of the rounding,
then we will output the resulting partition, and
the value will be the weighted sum of 1- XiXj / 2.
What we know is that because the quadratic relaxation is a relaxation,
opt is at most, the weighted sum 1- Vi.Vj / 2.
So our algorithm will be good if these two values are close to one another.
So we wish to round our quadratic program so
that 1- XiXj / 2 is similar to 1- Vi.Vj / 2.
How do we do this?
If you have two vectors, Vi and Vj, that are lined up,
if they are in the same position, then Vi.Vj equals 1.
They are unit vectors.
And then, this equals 0.
In that case, to have the same value here, what we want is Xi = Xj.
On the other hand, if the two vectors are opposites
like this, then 1- Vi.Vj / 2 equals 1, and
then what we want is we want the same thing to hold for Xi and Xj.
We want xi to be equal to -xj, so that this quantity is also equal to 1.
And if the vectors are everything in between, this is vi,
vj could be more or less lined up, more or less.
Then we cannot have exactly the same thing as this,
because this quantity will be something between -101.
So we want something that is close to it as possible.
So what we want is these two vectors to give us Xi, Xj,
that tend to be the same if the vectors tend to be lined up and
tend to be different if the vectors tend to be opposite.
We want far apart vectors to map to different values of Xi,
Xj, close by vectors to map to similar values of Xi and Xj.
So how do we do it?
The idea is, since here there's no clear way to do it, again,
when we don't know what to do, we use randomness.
We get to use randomized rounding.
Randomized rounding, right here, the idea is we're going to split the sphere,
the unit sphere in half using a random hyperplane.
Pick a random hyperplane H through the origin.
It randomly splits the sphere into two parts.
Above H, every vector that is above it goes to 1,
every vector that is below it goes to -1.
Then what happens?
Look at this, here's my hyperplane H.
If the two vectors are aligned up, Vi,
Vj, then, either they're both above or both below.
So either they will both map to 1 or both map to -1 and
therefore, we will have Xi = Xj as we desire.
Similarly, if the two vectors are opposite,
then regardless of how our hyperplane is oriented,
the two vectors will fall on different sides of the hyperplane.
And therefore, we will have one of the two values at 1 and
the other at -1 as desired.
And then if the two factors are somewhere in between, then the closer
they are together, the less likely it is that the hyperplane will fall in between,
and the more likely it is that Xi and Xj will be equal.
So that has a right feel.
So that's the algorithm.
First, we solve the quadratic vector program, the relaxation for
Maxcut, this gives us one unit length vector for each vertex,
then we pick one random hyperplane through the origin.
Every vector that is above the corresponding vertex maps to 1,
every vector that is below the corresponding vector maps to -1,
that defines the partition of our vertices of the two sets, and that's the output.
Only one question remains, how does one pick a random hyperplane?
Here is the way to do it.
Pick a point, uniformly at random on the unit sphere.
This point defines a vector, a unit length vector.
Take the normal hyperplane through the origin,
that's a hyperplane used to separate the vectors into two sets.
Okay, only one question remains still,
how do we pick a point uniformly at random on the unit sphere in high dimension?
In two dimensions, it's easy, the radius is 1,
the angle is uniform between 0 and 2pi.
In high dimensions, two ways to do it.
Either we say, we define the vector by defining Xi as an independent,
random variable drawn from the normal distribution with mean 0 and
standard deviation 1.
And then, we define the unit vector as X over the norm of X.
That's how we can define this vector.
Or we can use spherical coordinators.
Say the radius is 1, and all the angles are independent uniform.
So either way,
both of these things are valid techniques to pick a point on the unit sphere.
And so that defines our approximation algorithm for Maxcut.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
