Лекция 8
| Курс | Линейное программирование |
| Дата | 24.04.2011 - 11:15 - 12:50 |
| Аннотация | Задача о максимальном разрезе в ненаправленном графе. Рандомизированное 2-приближениеМаксимальный разрез как задача целочисленного квадратичного программирования. Переход к векторной и полуопределенным программам. Решение с помощью метода эллипсоидов, отделение от конуса неотрицательно определенных матриц. Округление с помощью метода случайных гиперплоскостей, оценка погрешности.Матроиды, примеры. Базы, их равномощность, ранговая функция. Жадный алгоритм поиска максимального по весу независимого множества. Политоп независимых множеств, прямая и двойственная программы. Явная конструкция оптимальных прямого и двойственного решения. Тотальная двойственная целочисленность политопа независимых множеств.
Lecture notes: http://www-math.mit.edu/~goemans/18433S09/matroid-notes.pdf, http://www-math.mit.edu/~goemans/18997-CO/co-lec9.ps, http://www-math.mit.edu/~goemans/18997-CO/co-lec10.ps, http://users.eecs.northwestern.edu/~nickle/combOpt/lec6.pdf, http://users.eecs.northwestern.edu/~nickle/combOpt/lec7.pdf, http://www.cs.cmu.edu/~anupamg/adv-approx/lecture14.pdf |
| Видео | http://lektorium.tv/lecture/?id=13283 |
Русский
English