Задачи с семинара 1

1. Задача о рюкзаке: дан рюкзак вместимости $C$, $n$ предметов объёмов $c_i$ и ценностей $p_i$. Вместить как можно больше суммарной ценности в рюкзак, не превысив суммарный объём.

   1) Алгоритм $\mathcal A$ — приближённая схема для задачи максимизации (approximation scheme, AS), если принимает на вход $x$ и $\varepsilon>0$ и выдаёт решение не меньше $(1-\varepsilon)\mathsf{OPT}$. Алгоритм $\mathcal A$ — приближённая схема полиномиального времени (polynomial-time approximation scheme, PTAS), если $\mathcal A$ — приближённая схема, для каждого фиксированного $\varepsilon$ работающая за полином от $|x|$. $\mathcal A$ — приближенная схема полностью полиномиального времени (fully polynomial-time approximation scheme, FPTAS), если $\mathcal A$ — приближённая схема, работающая за полином от $|x|$ и $\frac1\varepsilon$. FPTAS автоматически является PTAS, но не наоборот (например, время $\mathcal O\left(n^{\frac1\varepsilon}\right)$ допустимо для PTAS, но не для FPTAS). Алгоритм называется псевдополиномиальным, если он работает на входе $I$ за полиномиальное время от $\left|I_u\right|$, где $I_u$ — запись $I$, в которой все числа записаны в унарной системе счисления.

   2) Псевдополиномиальный алгоритм для задачи о рюкзаке. FPTAS для задачи о рюкзаке через псевдополиномиальный алгоритм и округление массива стоимостей.

2. Рассмотрим некоторые наивные методы приближения задачи о рюкзаке: отсортируем предметы в порядке:

   1) убывания $p_i$;

   2) возрастания $c_i$;

   3) убывания $\frac{p_i}{c_i}$.

   Будем их жадно брать в таком порядке. Можно ли получить $\alpha$-оптимальный ответ для некоторой константы $\alpha$? А можно ли получить $\alpha$-оптимальный ответ для вещественной версии задачи, в которой от каждого предмета можно взять долю $k_i\in[0;1]$ размером $k_ic_i$ и ценностью $k_ip_i$?

3. Наш алгоритм для cardinality vertex cover не $(2-\varepsilon)$-точен ни для какого $\varepsilon>0$.

4. Найти 2-приближение к задаче максимального паросочетания. Почему это не является $(2-\varepsilon)$-приближением?

5. Дан ориентированный граф $G=(V,A)$, найти наибольший набор стрелок $B\subseteq A$, на которых нет ориентированных циклов. Найти приближение, не более чем в константу раз худшее оптимального решения.

6. Предложим алгоритм для cardinality vertex cover: пока в графе не кончились рёбра, берём вершину максимальной степени, выкидываем её и инцидентные ей рёбра. В конце наше вершинное покрытие — множество выкинутых вершин. Почему алгоритм корректен? Какая точность полученного алгоритма?