4501
правка
Жадные алгоритмы аппроксимации: различия между версиями
Перейти к навигации
Перейти к поиску
Жадные алгоритмы аппроксимации (посмотреть исходный код)
Версия от 21:28, 23 апреля 2015
, 23 апреля 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
== Основные результаты == | == Основные результаты == | ||
Роль субмодулярности | '''Роль субмодулярности''' | ||
Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств | Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств <math>2^X \;</math>, то есть семействе всех подмножеств X. Функция f называется [[субмодулярная функция|субмодулярной]], если для любых двух подмножеств A и B в <math>2^X \;</math> выполняется неравенство | ||
f(A) + f(B) | |||
В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. | |||
<math>f(A) + f(B) \ge f(A \cap B) + f(A \cup B)</math>. | |||
В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. Функция -q(C), определенная в предыдущем разделе, является субмодулярной. Чтобы показать это, вначале рассмотрим свойства субмодулярных функций. | |||
Субмодулярная функция f называется [[нормализованная функция|нормализованной]], если <math>f( \empty ) = 0</math>. Каждая субмодулярная функция может быть нормализована посредством задания <math>g(A) = f(A) - f( \empty )</math>. Функция f является [[монотонно возрастающая функция|монотонно возрастающей]], если <math>f(A) \le f(B) \;</math> в случае <math>A \subset B \;</math>. Обозначим <math>\Delta_x f(A) = f(A \cup \{ x \} ) - f(A)</math>. | |||
Лемма 1. Функция f:2X!R является субмодулярной в том и только том случае, если Axf(A) < Axf(B) для любого x 2 X - B и A С B. Кроме того, f является монотонно возрастающей в том и только том случае, если Axf(A) < Axf(B) для любого x2B и ACB. | Лемма 1. Функция f:2X!R является субмодулярной в том и только том случае, если Axf(A) < Axf(B) для любого x 2 X - B и A С B. Кроме того, f является монотонно возрастающей в том и только том случае, если Axf(A) < Axf(B) для любого x2B и ACB. | ||
| Строка 148: | Строка 154: | ||
g < 2 ■ opt + i < opt 2 + ln | g < 2 ■ opt + i < opt 2 + ln | ||
где S – максимальная степень исходного графа G. | где S – максимальная степень исходного графа G. | ||
== Применение == | == Применение == | ||