Участник: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