4501
правка
Жадные алгоритмы аппроксимации: различия между версиями
Перейти к навигации
Перейти к поиску
Жадные алгоритмы аппроксимации (посмотреть исходный код)
Версия от 21:46, 23 апреля 2015
, 23 апреля 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
Напротив, предположим, что свойство (1) выполняется для любого <math>x \in B \;</math> и <math>A \subseteq B \;</math>. Пусть C и D – два множества и <math>C \setminus D = \{ x_1, ..., x_k \}</math>. Тогда | Напротив, предположим, что свойство (1) выполняется для любого <math>x \in B \;</math> и <math>A \subseteq B \;</math>. Пусть C и D – два множества и <math>C \setminus D = \{ x_1, ..., x_k \}</math>. Тогда | ||
<math>f(C \cup D) - f(D) = \sum_{i=1}^k \Delta_{x_i} f(D \cup \{ x_1, ..., x_{i - 1} \} )</math> <math>\le \sum_{i=1}^k \Delta_{x_i} f((C \cap D) \cup \{ x_1, ..., x_{i - 1} \} )</math> <math>= f(C) - f(C \cap D)</math>. | |||