Просмотр исходного текста страницы Участник:Kirillskor/minimum-multicover-approx-with-linear-relaxation

[[Жадный алгоритм в задачах о покрытии/Задачи/minimum-multicover-approx-with-linear-relaxation]]

<latex>

Сведем задачу к задаче линейного программирования:

$\min_x \sum_{i=1}^{m} \omega_i x_i$, при ограничениях $x \in \{0, 1\}, \sum_{j=1}^{m} a_{ij} x_j \geq b_i$

\vspace{3mm}
Релаксация этой задачи:
$\min_x \sum_{i=1}^{m} \omega_i x_i$, при ограничениях $0 \leq x_i \leq 1, \sum_{i=1}^{m} a_{ij} x_j \geq b_i$

Обозначим за $x^*$ решение релаксации задачи.

Пусть $x$ получается из $x^*$ округлением элементов больше 1 / P к 1, и всех остальных к 0.

Докажем что такое решение будет P-оптимальным.

Сначала покажем что такое округление $x^{lp}$ удовлетворяет исходным ограничениям:

Пусть сущесвует такое i, что $s_i$ не принадлежит нашем покрытию достаточное число раз, тогда $\sum_{j=1}^{m} a_{ij} \leq (b_i - 1)$, но
 

$\sum_{j=1}^{m} a_{ij} x_j^* = \sum_{j: x_j \geq 1 / p}^{m} a_{ij} x_j^*  + \sum_{j: x_j < 1 / p}^{m} a_{ij} x_j^* < (b_i - 1) + 1 < b_i$ - противоречие с ограничениями задачи релаксации.

<\latex>