Участник:Kirillskor/minimum-multicover-approx-with-linear-relaxation — различия между версиями
Материал из DISCOPAL
Строка 2: | Строка 2: | ||
− | Сведем задачу к задаче линейного программирования | + | Сведем задачу к задаче линейного программирования: |
<latex> | <latex> | ||
− | $\min_x \sum_{i=1}^{m} \omega_i x_i$, при ограничениях $ | + | $\min_x \sum_{i=1}^{m} \omega_i x_i$, при ограничениях $x \in \{0, 1\}, \sum_{i=1}^{m} a_{ij} x_j \geq b_i$ |
+ | Релаксация этой задачи: | ||
+ | $\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$ | ||
+ | Решаем | ||
<\latex> | <\latex> |
Версия 00:14, 14 декабря 2017
Жадный алгоритм в задачах о покрытии/Задачи/minimum-multicover-approx-with-linear-relaxation
Сведем задачу к задаче линейного программирования: