Участник:Kirillskor/minimum-multicover-approx-with-linear-relaxation — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
 
(не показано 8 промежуточных версий 1 участника)
Строка 1: Строка 1:
 
[[Жадный алгоритм в задачах о покрытии/Задачи/minimum-multicover-approx-with-linear-relaxation]]
 
[[Жадный алгоритм в задачах о покрытии/Задачи/minimum-multicover-approx-with-linear-relaxation]]
  
 
Сведем задачу к задаче линейного программирования.
 
  
 
<latex>
 
<latex>
$\min \sum{i=1}_{m}$
+
 
 +
Сведем задачу к задаче линейного программирования:
 +
\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$
 +
 
 +
\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$
 +
 
 +
Обозначим за $x^*$ решение релаксации задачи.
 +
\vspace{3mm}
 +
 
 +
Пусть $x^{lp}$ получается из $x^*$ округлением элементов больше 1 / P к 1, и всех остальных к 0.
 +
 
 +
Докажем что такое решение будет P-оптимальным.
 +
\vspace{3mm}
 +
 
 +
Сначала покажем что такое округление $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$ - противоречие с ограничениями задачи релаксации(2ую сумму оценили из определения P).
 +
 
 +
Теперь докажем, что полученная стоимость не больше чем в P раз хуже оптимальной:
 +
 
 +
$\sum_{i = 1}^{m} x_i^{lp} \omega_i \leq \sum_{i = 1}^{m} P x_i^* \omega_i = P * opt$, где opt - оптимальная стоимость в релаксации задачи, то есть не хуже оптимальной стоимости в исходной целочисленной задаче.
 +
 
 +
Значит нашли P-оптимальное решение.
 
<\latex>
 
<\latex>
 +
 +
[[Категория:Решения]]

Текущая версия на 15:22, 17 декабря 2017

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