Участник:Kirillskor/minimum-multicover-approx-with-linear-relaxation — различия между версиями
Материал из DISCOPAL
Строка 5: | Строка 5: | ||
Сведем задачу к задаче линейного программирования: | Сведем задачу к задаче линейного программирования: | ||
− | $\min_x \sum_{i=1}^{m} \omega_i x_i$, при ограничениях $x \in \{0, 1\}, \sum_{ | + | $\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} | \vspace{3mm} | ||
Строка 16: | Строка 16: | ||
Докажем что такое решение будет P-оптимальным. | Докажем что такое решение будет 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> | <\latex> |
Версия 00:39, 14 декабря 2017
Жадный алгоритм в задачах о покрытии/Задачи/minimum-multicover-approx-with-linear-relaxation