Участник:Kirillskor/minimum-multicover-approx-with-linear-relaxation — различия между версиями
Материал из DISCOPAL
| Строка 4: | Строка 4: | ||
Сведем задачу к задаче линейного программирования: | Сведем задачу к задаче линейного программирования: | ||
| + | \vspace{3mm} | ||
$\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$ | $\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$ | ||
| Строка 9: | Строка 10: | ||
\vspace{3mm} | \vspace{3mm} | ||
Релаксация этой задачи: | Релаксация этой задачи: | ||
| + | \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$ | $\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^*$ решение релаксации задачи. | ||
| + | \vspace{3mm} | ||
| − | Пусть $x$ получается из $x^*$ округлением элементов больше 1 / P к 1, и всех остальных к 0. | + | Пусть $x^{lp}$ получается из $x^*$ округлением элементов больше 1 / P к 1, и всех остальных к 0. |
Докажем что такое решение будет P-оптимальным. | Докажем что такое решение будет P-оптимальным. | ||
| + | \vspace{3mm} | ||
Сначала покажем что такое округление $x^{lp}$ удовлетворяет исходным ограничениям: | Сначала покажем что такое округление $x^{lp}$ удовлетворяет исходным ограничениям: | ||
Версия 00:49, 14 декабря 2017
Жадный алгоритм в задачах о покрытии/Задачи/minimum-multicover-approx-with-linear-relaxation