Приближённые алгоритмы

  1. [15 минут] Коммивояжёр
    1. 2 приближение через MST
    2. 1.5 приближение через MST
  2. [15 минут] Жадное приближение для set cover (покрыть множество множествами)
  3. [15 минут] Жадное приближение для bin packing (разбить на минимальное число рюкзаков все вещи; FFD, BFD, 11/9, не существование приближения)
    4. --- Перерыв ---
  4. [10 минут] Хорновские формулы (определение: не более одного отрицания в каждом дизъюнкте; решение: жадно или все 1, или есть одинокое отрицание)
  5. [35 минут] Одна сложная задача
    1. Задача: выполнить максимум работ с дедлайнами
    2. Выполнять, мы уже знаем, нужно в порядке возрастания ti + di. Кого выполнять?
    3. Динамика ΣT[i,k] за O(n2)
    4. Жадность "пытаться брать или заменить" за O(nlogn)
    5. Отличие жадности: поддерживаем Σk[i] только для максимального k
    6. Почему так можно делать? Инвариант A1i ⊂ A2i ⊂ ... ⊂ ... Aki