ConvAppr19

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

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

Лекции проходят по понедельникам в аудитории 301, время 9:00-10:20. Семинары - в той же аудитории, время 10:30-11:50. Первое занятие 14 января. Последнее занятие 18 марта.

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

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·Оэкз, где Онакопленная =Одз.

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

Литература

  1. Вялый М.Н. Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность. Черновик учебника.
  2. Barak, Boaz. Steurer, David. (2016) Proofs, beliefs, and algorithms through the lens of sum-of-squares. https://www.sumofsquares.org/public/index.html
  3. 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/
  4. Trevisan, Luca (2016). CS294: Graph Partitioning, Expanders and Spectral Methods. UC Berkeley. https://people.eecs.berkeley.edu/~luca/expanders2016/index.html#notes
  5. Vazirani Vijay V. (2003). Approximation Algorithms. Springer-Verlag Berlin Heidelberg.


Рефераты

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

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

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

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

  1. Реферат по статье, в которой показана разница между задачей оценки оптимального значения целевой функции и нахождением приближенного допустимого решения. 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.
  2. Реферат о нижних оценках точности релаксаций Шерали-Адамса для задачи о максимальном разрезе по статье 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.
  3. Реферат об алгоритмах достижения оценок в общих задачах выполнимости, которые превосходят среднее, по статье 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. (Примечание: трудная тема, требует достаточно свободного владения анализом Фурье для булевых функций.)
  4. Реферат об алгоритме рекордной на данный момент точности для задачи 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.
  5. Реферат о достижимости оценки Гёманса-Вильямсона по статье 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.

Лекции

Семинары