Жадности, приближения, PTAS-ы (12 марта 2021)

1. Крутая жадность с заменами
   1. Задача: даны дедлайны окончания d_i и времена исполнения t_i
   2. Выбрать макс число задач за O(n²). Сортировка по d_i + динамика minSumT[i,k].
   3. Выбрать макс число задач за O(nlogn). Жадность с заменами: поддерживаем minSumT только для максимально возможного maxK.
   4. Доказательство: на самом деле мы знаем весь слой динамики, ответ для каждого k ≤ maxK : minSumT[i,k] − это первые k в сортировке по t_i maxK выбранных.
   5. Применяем доказательство к задаче: спортсмены с силой s_i, массой m_i выстраиваются в башню. Выстроить всех: сортировка по s_i+m_i.
   
   
2. Жадности и приближения
   1. Set Cover ln(n)-OPT.
   2. [skipped] [ушло в практику] взвешенный случай Set Cover
   3. [skipped] [Ушла в практику] Надстрока (жадное решение)
   4. [skipped] [Ушла в практику] Хорновские формулы (определение: не более одного отрицания в каждом дизъюнкте; решение: жадно или все 1, или есть одинокое отрицание)
   
   
3. Рюкзаки, PTAS-ы для knapsack
   1. Задачи: partition, subsetsum, knapsack, binpacking. Целочисленность, вещественность.
   2. NP-трудоность: сводим решаем partition через любую из subsetsum, knapsack, binpacking
   3. Определяем PTAS и FPTAS (приближение для любого ε)
   4. [skipped] [ушло в практику] PTAS для рюкзака без стоимостей (partition).
   5. Рюкзак со стоимостями (knapsack)
      1. Проблема обычной жадности по w_i/p_i: никак не приближает
      2. PTAS (1+1/k) приближение (переберём какие k точно возьмём за n^k)
      3. FPTAS: динамика maxProfit[i, weight] и minWeight[i, profit]. Берём вторую динамику и делим профиты всех предметов на K.
   
   
4. Жадное решение для partition
   1. Что собственно хочется приближать? |sum(a_i)-sum(b_i)| плохо, max(sum(a_i), sum(b_i))
   2. Жадность: sort(w_i), класть в меньший из двух
   3. Понимание того, что это 6/5-OPT: n=4 предмета мы всегда решим оптимально, далее разность не более a₅ ⇒ ошибка не более a₅/2
   4. На самом деле это 7/6-OPT