И.А. Близнец, "Вероятностные алгоритмы"
План занятий:
1) Минимальный разрез. Параметризованный алгоритм для наибольшего дерева.
2) Неравенство Маркова и Чебышева. Задача о стабильных браках
3) Задача о собирателях купонов.
4) Оценки Чернова, покраска гиперграфов.
5) Оценки Чернова, округление решений.
6) Вероятностные методы в применении к MAXSAT.
7) Метод условной вероятности.
8) Расширяющиеся графы.
9) Кодирование цветом. d - кластеризация
10) Методы дерандомизации.
11) Мотонный локальный поиск
12) Ядро для MAX-R-SAT
13) Локальная лемма Ловаса
14) Алгебраические методы
15) Согласованное хэширование. Выбор лидера.
16) Метод случайной проекции
Литература:
1) Rajeev Motwani and Prabhakar Raghaven, Randomized algorithms.
2) Cygan et al, Parameterized algorithms.
3) Vijay Vazirani, Approxamation algorithms
4) Noga Alon and Joel Spenser, The Probabilistic Method.
5) Mitzenmacher and Upfal, Probability and Computing.
