Центроидная декомпозиция и окончание прошлой лекции (24 марта 2018)

  1. [20 минут] Более сложная жадность −- "выбрать макс число спортсменов"
    1. Жадное решение за O(nlogn)
    2. Решение за O(n2) динамикой
    3. Доказываем жадность через динамику

  2. [10 минут] PTAS/FPTAS. Определения.

  3. [30 минут] Рюкзаки
    1. Рюкзак без стоимостей (partition).
      1. Жадное решение (7/6 OPT)
      2. PTAS: (1+1/k)-OPT (доказательство ушло в практику)
      3. Алгоритм Кармаркар-Карпа (1982).
    2. Рюкзак со стоимостями (knapsack)
      1. Проблема обычной жадности: никак не приближает
      2. PTAS (1+1/k) приближение (переберём какие k точно возьмём за nk)
      3. FPTS: динамика maxProfit[i, weight] и minWeight[i, profit]. Берём вторую динамику и делим профиты всех предметов на K.
    3. Мультирюкзак (bin packing)
      1. Сложность приближения: определить 2 или 3 − уже NP-hard (partition)
      2. Зато сделать 2 приближение очень просто: first fit.
      3. first fit decresing и best fit decresing (11/9*OPT+1 приближение)
      4. PTAS для bin packing: 1 + OPT(1+ε)
      5. [skipped] Олимпиадные задачи (например, timus-1144) показывают, что в k-bin packing эффективна эвристика "локальные оптимизации случайного распределения"
− Перерыв −
  1. [skipped] [Ушла в практику] Надстрока
  2. [skipped] [Ушла в практику] Хорновские формулы (определение: не более одного отрицания в каждом дизъюнкте; решение: жадно или все 1, или есть одинокое отрицание)

  3. [10 минут] Set cover ln(n)-OPT.
    1. [skipped] [ушло в практику] взвешенный случай

  4. [30 минут] Центроидная декомпозиция
    1. Определение (дерево центров, дерево компонент связности)
    2. Построение за O(nlogn) с кодом, хранение за O(n), выражение path(a,b) в виде суммы path(a,center)+path(center,b)
    3. Предподсчёт функции, удобное хранение (добавляем глубину в построение).