28.11.2017 Приближённое решение задачи о раскраске (Надежда Воронова)

Название: Приближённое решение задачи о раскраске

Время: 28 ноября, 16:30

Место: ПОМИ РАН, аудитория 402

Докладчик: Воронова Надежда

Описание:

Мы рассмотрим задачу покраски k-раскрашиваемого графа в наименьшее число цветов. 

Для этого будут рассмотрены связанные задачи, такие как векторная k-раскраска и полураскраска, их связь с исходной задачей и решение с помощью полуопределённого программирования, которое будет использоваться как "чёрный ящик". 

Получим рандомизированный алгоритм для раскраски 3-раскрашиваемого графа за полиномиальное время, используя O(n^0.387) цветов.

Если останется время, то рассмотрим обобщенную версию подобного алгоритма для k-раскрашиваемых графов.

 

Доклад по 

David Karger, Rajeev Motwani, Madhu Sudan 

"Approximate Graph Coloring by Semidefinite Programming"

http://madhu.seas.harvard.edu/papers/1994/kms-journ.pdf