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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 22: Строка 22:
 
   
 
   
  
$\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$ - противоречие с ограничениями задачи релаксации.
+
$\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>

Версия 00:46, 14 декабря 2017

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