imported>Vyalyi: Migrated current public revision from wiki.cs.hse.ru

2019-03-18T14:00:36Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

= Выпуклое программирование и аппроксимационные алгоритмы (ТИ)=

'''Внимание: регулярное расписание изменилось!'''

Лекции проходят по понедельникам в аудитории 400, время 12:10-13:30. Семинары - в аудитории 513, время 13:40-15:00. Первое занятие 14 января. Последнее занятие 18 марта.

'''Изменения расписания:'''

21 января: семинар пройдет в 618 аудитории, время то же 13:40-15:00.

14 января: лекция - ауд. 301, 10:30-11:50, семинар - ауд. 435, 12:10-13:30.

'''[https://www.dropbox.com/s/nwiazv80wobt0xl/156.xls?dl=0 Таблица результатов] '''

'''Экзамен:''' 25 марта (понедельник), 12:00-15:00, ауд. 300.

'''[https://www.dropbox.com/s/9yzybb1qmghvtvk/exam-program.pdf?dl=0 Программа экзамена и правила проведения.]'''

==Преподаватель==

М.Н. Вялый vyalyi@gmail.com

Основной предмет изучения в курсе: приближенные алгоритмы для задач комбинаторной оптимизации, основанные на решении выпуклых релаксаций задачи.

== Содержание курса==

* Средние оценки и дерандомизация

* ЛП релаксации

* Иерархия Шерали-Адамса (SA)

* Задача об относительном разрезе, задача о вложении метрик. Теорема Бургейна.

* Иерархия Лассера (LA)

* Округление Гёманса-Вильямсона: для задач MAX-CUT, MAX-2SAT. Неравенство Гротендика. Приближенный алгоритм вычисления нормы разрезов.

* Гауссовы округления и задача квадратичного программирования на булевом кубе.

* LA релаксации для плотных случаев задачи MAX-CUT.

* Нижние оценки точности LA релаксаций линейной степени для задачи MAX3LIN.

==Правила оценивания ==

Оценки текущего и итогового контроля выставляются по 10-ти балльной шкале.

Оценка текущего контроля - это оценка за выполнение домашнего задания. Домашнее задание состоит в записи решений задач, как разбиравшихся на семинарах, так и оставленных для самостоятельного решения. Сдавать записанные решения необходимо в сроки, указанные преподавателем. За оригинальные и/или очень ясные решения задач предусмотрены бонусные баллы.

Оценка ''Одз'' за домашнее задание пропорциональна с коэффициентом 1/8 количеству баллов и бонусных баллов, полученных за решения задач, если это количество не превосходит 80 (в противном случае оценка равна 10).

Оценка итогового контроля ''Оэкз'' выставляется либо за сдачу устного экзамена в классической форме (теоретический вопрос, задача), либо за защиту реферата по предложенной преподавателем статье. В этом случае необходим как письменный текст реферата, так и беседа по содержанию статьи. Последняя может быть заменена докладом на семинаре.

''Оитог'' = 0,25·''Онакопленная'' + 0,75·''Оэкз'', где ''Онакопленная'' =''Одз''.

Экзаменационная оценка выставляется одним из двух способов, по выбору студента: либо за сдачу устного экзамена, либо за защиту реферата.
Округление результирующей оценки арифметическое.

==Литература ==

# Вялый М.Н. Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность. [https://www.dropbox.com/s/jp4rmi9m1ian4rr/approx-lec.pdf?dl=0 Черновик учебника.]
# Barak, Boaz. Steurer, David. (2016) Proofs, beliefs, and algorithms through the lens of sum-of-squares. https://www.sumofsquares.org/public/index.html
# Gupta, Anupam. O'Donnell Ryan. (2008) 15-854(B): Advanced Approximation Algorithms. Carnegie Mellon's School of Computer Science. https://www.cs.cmu.edu/~anupamg/adv-approx/
# Trevisan, Luca (2016). CS294: Graph Partitioning, Expanders and Spectral Methods. UC Berkeley. https://people.eecs.berkeley.edu/~luca/expanders2016/index.html#notes
# Vazirani Vijay V. (2003). Approximation Algorithms. Springer-Verlag Berlin Heidelberg.

= Рефераты =

Реферат готовится в письменном виде и затем устно защищается: либо на регулярном экзамене, либо на семинаре (по выбору преподавателя).

Идеальный реферат должен объяснять

* Постановку задачи, решаемой в статье.

* Важность этой задачи для теории приближенных алгоритмов (теории сложности), возможные приложения.

* Полученные в статье результаты, их сравнение с другими известными результатами в этой области.

* Технику, использованную в доказательствах.

Ниже приводятся темы рефератов и указано, кто из студентов выбрал тему. Список не полный и постепенно расширяется. По всем вопросам, связанным к с выбором темы реферата и его подготовкой, обращаться к преподавателю.

# '''(взят М.Дискиным) ''' Реферат по статье, в которой показана разница между задачей оценки оптимального значения целевой функции и нахождением приближенного допустимого решения. Uriel Feige and Shlomo Jozeph. 2015. Separation between Estimation and Approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS '15). ACM, New York, NY, USA, 271-276.
# Реферат о нижних оценках точности релаксаций Шерали-Адамса для задачи о максимальном разрезе по статье Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu. 2007. Linear programming relaxations of maxcut. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '07). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 53-61.
# Реферат об алгоритмах достижения оценок в общих задачах выполнимости, которые превосходят среднее, по статье Beating the random assignment on constraint satisfaction problems of bounded degree. / Barak, Boaz; Moitra, Ankur; O'Donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Vol. 40 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. p. 110-123. (Примечание: трудная тема, требует достаточно свободного владения анализом Фурье для булевых функций.)
# '''(взят Я.Ребенко)''' Реферат об алгоритме рекордной на данный момент точности для задачи MAX-2SAT по статье M. Lewin, D. Livnat, and U. Zwick. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In IPCO, pages 67-82, 2002.
# '''(взят В.Гринбергом)''' Реферат о достижимости оценки Гёманса-Вильямсона по статье U. Feige and G. Schechtman. On the optimality of the random hyperplane rounding technique for max cut. Random Struct. Algorithms, 20(3):403--440, 2002.
# '''(взят Е.Минеевой)''' Реферат о неожиданных возможностях релаксаций Шерали-Адамса по недавней статье Ryan O’Donnell, Tselil Schramm. Sherali–Adams Strikes Back. https://arxiv.org/abs/1812.09967v1
# '''(взят А.Стороженко)''' Реферат о нижних оценках точности релаксаций Шерали-Адамса для нескольких задач (включая sparsest cut) по статье Moses Charikar, Konstantin Makarychev, and Yury Makarychev. 2009. Integrality gaps for Sherali-Adams relaxations. In Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC '09). ACM, New York, NY, USA, 283-292.
# Реферат о применении релаксаций Шерали-Адамса в теории расписаний по статье Elaine Levey, Thomas Rothvoss. A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies. arXiv:1509.07808v2
# Реферат о нижних оценках точности аппроксимаций Лассера для задачи о скрытой клике по статье Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. arXiv:1604.03084v2 [cs.CC] 12 Apr 2016

=Лекции =

'''18 марта''' Гауссово окрругление. Задача квадратичного программирования на (+1,-1) кубе. Точность релаксаций Лассера 2й степени для задачи о максимальном независимом множестве.

'''11 марта''' Неравенство Гротендика. Приближенный алгоритм оценки нормы разрезов матрицы.

'''4 марта''' Округление Гёманса - Вильямсона для задач MAX-CUT, MAX2SAT.

'''25 февраля''' Иерархия Лассера. Псевдораспределения. Задача линейной оптимизации на конусе неотрицательно определенных матриц и ее связь с релаксациями Лассера.

'''18 февраля''' Доказательство теоремы Бургейна

'''11 февраля''' Задача об относительном разрезе (the sparsest cut). Релаксация Лейтона-Рао. Оценка точности этой релаксации с помощью теоремы Бургейна.

'''4 февраля''' Уточнение определений, связанных с квазираспределениями. Метрические неравенства на уровне 3 иерархии SA. Многогранник разрезов и формулировка задачи MAX-CUT в виде максимизации квадратичной функции на булевом кубе.

'''28 января''' Квазираспределения. Иерархия Шерали-Адамса (SA). Точность иерархии SA.

'''21 января''' Усреднение для задачи MAX-QP: выбор неравномерного распределения. От усреднения к релаксациям задач ЦЛП. Оценки точности релаксаций: вершинное покрытие, общее покрытие, задача MAX-SAT.

'''14 января''' Приближенные алгоритмы и их качество: точность релаксации, мультипликативная погрешность. Усреднение. Примеры задач, для которых усреднение дает хорошие приближенные алгоритмы, и таких задач, для которых использование усреднения затруднительно.

=Семинары =

'''[https://www.dropbox.com/s/6869l7a0gtujl71/pr09CA.pdf?dl=0 Задачи 9го занятия]''' Отредактированная версия листка, разбиравшегося на семинаре. Решения этих задач принимаются в электронном виде (формат pdf) до 17.03, 23:59.59 (GMT +3).

'''[https://www.dropbox.com/s/457sdtznhddf6w1/pr08CA.pdf?dl=0 Задачи 8го занятия]''' Расширенная версия. Добавлена задача 7.6, относящаяся к предыдущему листку. Решения этих принимаются в электронном виде (формат pdf) до 10.03, 23:59.59 (GMT +3).

'''[https://www.dropbox.com/s/5hdj7xumtis9sft/pr07CA.pdf?dl=0 Задачи 7го занятия]''' Решения задач 7.1--7.4 принимаются до 03.03, 23:59.59 (GMT +3). Решение задачи 7.5 принимается до конца модуля (бонус можно получить даже за точную ссылку на текст решения).

'''[https://www.dropbox.com/s/qyn4x4pugikcmx4/pr06CA.pdf?dl=0 Задачи 6го занятия]''' Решения этих задач принимаются в электронном виде (формат pdf) до 24.02, 23:59.59 (GMT +3).

'''[https://www.dropbox.com/s/at8nkkvkedr6a5i/pr05CA.pdf?dl=0 Задачи 5го занятия]''' Отредактированная версия листка, разбиравшегося на семинаре. Решения этих задач принимаются до 17.02, 23:59.59 (GMT +3).

'''[https://www.dropbox.com/s/814c8p9zo8yepz0/pr04CA.pdf?dl=0 Задачи 4го занятия]''' Отредактированная и сокращённая версия листка, разбиравшегося на семинаре. Решения задач 1, 2 из этого листка принимаются до 10.02, 23:59.59 (GMT +3). Решения задач 3*, 4* принимаются до конца модуля.

'''[https://www.dropbox.com/s/dyodnctjtizfznx/pr03CA.pdf?dl=0 Задачи третьего занятия]''' По сравнению с листком на семинаре состав задач расширен, условия отредактированы.
Решения задач 1--3, 5, 8a принимаются в электронном виде (формат pdf) до
03.02, 23:59.59 (GMT +3). Решения остальных задач принимаются до 10.02, 23:59.59 (GMT +3).

'''[https://www.dropbox.com/s/1lbqtvbkd81s5v9/pr02CA.pdf?dl=0 Задачи второго занятия]''' Решения этих задач принимаются в электронном виде (формат pdf) до 27.01, 23:59.59 (GMT +3).

'''[https://www.dropbox.com/s/bsxaeksq2d1u2go/pr01CA.pdf?dl=0 Задачи первого занятия]''' Решения этих задач принимаются в электронном виде (формат pdf) до 20.01, 23:59.59 (GMT +3).

ConvAppr19 - История изменений

imported>Vyalyi: Migrated current public revision from wiki.cs.hse.ru