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

1. Определение двойственной задачи. Слабая и сильная теорема о двойственности. Постройте прямую и двойственную задачу для:

   а) задачи о поиске максимального потока;

   б) задачи о поиске максимального дробного паросочетания.

   Слабая и сильная теоремы о двойственности.

2. Определение тотально унимодулярной матрицы. Матрица инцидентности графа тотально унимодулярна тогда и только тогда, когда он двудольный.

3. Напомним задачу Set cover. Пусть $V={1,2,\ldots,n}$, и $\mathcal S\subseteq2^V$ — набор множеств, покрывающий $V$: $\bigcup\limits_{S\in\mathcal S}{S}=V$. Пусть, кроме того, задана ценовая функция $c_\cdot\colon\mathcal S\to\mathbb N$, действующая по правилу $S\mapsto c_S$.

   Теперь определим ценность набора множеств $\mathcal T\subseteq\mathcal S$ как $c_\mathcal T=\sum\limits_{S\in\mathcal T}{c_S}$. Назовём набор допустимым, если $\bigcup\limits_{S\in\mathcal T}{S}=V$. Задача заключается в том, чтобы найти допустимый набор наименьшей ценности.

   а) Докажите, что следующая задача целочисленного линейного программирования решает Set cover: $$ \cases{ x_S\in\mathbb N_0&$S\in\mathcal S$\ \sum\limits_{S\ni i}{x_S}\geqslant1&$i\in V$\ \min\sum\limits_{S\in\mathcal S}{c_Sx_S} } $$ Назовём оптимальный ответ в этой задаче $\mathsf{OPT}_I$. Её ослаблением является следующая задача линейного программирования: $$ \cases{ x_S\geqslant0&$S\in\mathcal S$\ \sum\limits_{S\ni i}{x_S}\geqslant1&$i\in V$\ \min\sum\limits_{S\in\mathcal S}{c_Sx_S} } $$ Назовём оптимальный ответ в ослаблении $\mathsf{OPT}$; очевидно, $\mathsf{OPT}\leqslant\mathsf{OPT}_I$.

   б) Пусть $f$ — наибольшее количество раз, которое какой-то из элементов входит в множества из $\mathcal S$. Докажите, что следующий приближённый алгоритм для Set Cover корректный и выдаёт коллекцию множеств стоимости не более $f\mathsf{OPT}$: решить задачу линейного программирования, получить вектор чисел $x\in[0;1]^{\mathcal S}$ и взять в покрытие те множества $S$, у которых $x_S\geqslant\frac1f$. Таким образом, это $f$-точный полиномиальный алгоритм для Set Cover.