Просмотр исходного текста страницы ConvAppr19

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

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

Лекции проходят по понедельникам в аудитории 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.

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

М.Н. Вялый 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

=Лекции  =

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

=Семинары =

'''[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).