Explore
For Enterprise
Join for Free
Log In

Гуманитарные науки и искусства
Бизнес
Компьютерные науки
Наука о данных
Информационные технологии
здоровье
Математика и логика
Личное развитие
Естественные и технические науки
Социальные науки
Изучение языков
Степени
Сертификаты

Полный обзор Coursera

Обзор
Поиск
Для организаций
Войти
Присоединиться бесплатно

A rounding algorithm

Loading...

Approximation Algorithms Part II

Высшая нормальная школа

4.8 (оценок: 43) | Зарегистрировано учащихся: 7.2K

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.

Просмотреть программу курса

Рецензии

4.8 (оценок: 43)

5 stars
38 ratings
4 stars
3 ratings
3 stars
1 ratings
2 stars
1 ratings

AP

Oct 28, 2016

Demanding course with lots of great algorithm concepts based on Linear Programming.

DA

Mar 01, 2018

I really appreciate your valuable knowledge sharing. This is a perfect course.

Из урока

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.

A rounding algorithm7:18

Преподаватели

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., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play

Coursera
О проекте
Руководство
Карьера
Каталог
Сертификаты
Сертификаты MasterTrack™
Степени
Для организаций
Для правительственных организаций

Сообщество
Learners
Partners
Developers
Beta Testers
Translators

На связи
Блог
Facebook
LinkedIn
Twitter
Instagram
YouTube
Технический блог

Еще
Условия
Конфиденциальность
Помощь
Доступность
Пресса
Контакты
Справочник
Филиалы