Задачи с семинара 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: пока в графе не кончились рёбра, берём вершину максимальной степени, выкидываем её и инцидентные ей рёбра. В конце наше вершинное покрытие — множество выкинутых вершин. Почему алгоритм корректен? Какая точность полученного алгоритма?