Рассмотрим задачу о покрытии множества (Set Cover) и её линейную программу. Пусть количество множеств в семействе равно m, также пусть максимальное перекрытие множеств семейства равно f. Рассмотрим x1, x2, . . . , xm – решение линейной программы. На

Для решения данной задачи о покрытии множества (Set Cover) и доказательства того, что округление $\hat{x}i = I{x_i 0}$ также дает $f$-приближение, мы будем следовать нескольким шагам.

Шаг 1: Понимание задачи

Задача о покрытии множества заключается в том, чтобы выбрать минимальное количество подмножеств из заданного семейства, чтобы покрыть все элементы. Линейная программа (ЛП) для этой задачи может быть записана в следующем виде:

$
\text{minimize} \sum{i=1}^{m} xi
$
при условиях:
$
\sum{i: e \in Si} x_i \geq 1 \quad \forall e \in U
$
$
x_i \geq 0 \quad \forall i
$

где $U$ — это множество элементов, а $S_i$ — подмножества.

Шаг 2: Округление $\bar{x}_i$

На семинаре было показано, что округление $\bar{x}i = I{xi \g...i$ больше или равно $1/f$, то мы выбираем это множество, иначе — нет.

Теперь рассмотрим округление \hat{x}{xi больше нуля.

1. : Рассмотрим любое множество $S_j$, которое покрывает элемент $e$. По условиям линейной программы, для каждого элемента $e$ выполняется:

   \sumi} x_i \geq 1
   Пусть $k$ — количество множеств, которые покрывают элемент $e$. Тогда:
   \sumi} x_i \geq 1
   Это означает, что сумма $x_i$ по всем множествам, которые покрывают $e$, должна быть не менее 1.

2. : Если $xi$ должно быть больше некоторого значения, которое зависит от $f$. В частности, если $k$ множеств покрывают элемент $e$, то по линейной программе:

   \sumi} xi \geq \frac{1}{k}
   Если $k \leq f$, то:
   \sumi} xi \geq \frac{1}{f}

3. : Если мы выбираем все множества, для которых $x_i 0$, то количество выбранных множеств будет не больше $f$ раз больше, чем минимальное количество множеств, необходимых для покрытия элемента $e$.

Таким образом, если мы выбираем все множества, для которых xi = Ii 0} также дает $f$-приближение для задачи о покрытии множества.

Таким образом, мы пришли к выводу, что округление $\hat{x}_i$ действительно является $f$-приближением.