Задачи с семинара 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.