0. Центроиды (на примере задачи "мин на пути")
0.1 Концепция, решение, некоторые технические моменты

1. Доказываем Хаффмана

2. Максимизируем число выполненных задач"
2.1 Решение за O(n^2) динамикой
2.2 Жадное решение за O(nlogn)
2.3 Доказываем жадность через динамику

3. Про приближенные алгоритмы: просто алгоритмы и A.S.
3.1 Def. PTAS, FPTAS
3.2 Задачки, которые будем решать: Partition, Knapsack, Bin Packing.
3.3 Сводим Partition -> Knapsack, BinPack
3.4 Замечаем, что определить в binpack 2 или 3 − уже NP-hard

4. Partition
4.1 Жадное решение: 7/6 OPT, ошибка не более a5.
4.2 PTAS: (1+1/k)-OPT (доказательство ушло в практику)
4.3 [skipped] Алгоритм Кармаркар-Карпа (1982).

5. Рюкзак со стоимостями (knapsack)
5.1 Проблема обычной жадности: никак не приближает
5.2 PTAS (1+1/k) приближение (переберём какие k точно возьмём за nk)
5.3 FPTAS: динамика maxProfit[i, weight] и minWeight[i, profit].
5.4 Берём вторую динамику и делим профиты всех предметов на K.

6. [skipped] Bin packing
6.1 [skipped] Понимаем, что приближения (<1.5) не видать.
6.2 [skipped] Зато сделать 2 приближение очень просто: first fit.
6.3 [skipped]first fit decresing и best fit decresing (11/9*OPT+1 приближение)
6.4 [skipped] PTAS для bin packing: 1 + OPT

7. Set Cover, ln(n)-приближение в невзвешенном случае.