Линейное программирование Задача о покрытии

Задача «Покрытие» Дано: Совокупность U из n элементов, и набор подмножеств U, Ω = {S 1,…, S k }, и веса(стоимости) подмножеств c: Ω Q +. Найти покрытие наименьшего веса. Ω' Ω является покрытием, если любой элемент из U принадлежит хотя бы одному элементу из Ω'.

Кратность Пусть f i – кратность элемента e i, то есть число множеств из Ω, в которые он входит. Пусть f = max i=1,…,n f i.

ЦЛП (Задача о покрытии)

ЛП-релаксация (Задача о покрытии)

Алгоритм «Округление ЛП-релаксации» 0) Input (U, Ω, c: Ω Q + ) 1) Найти оптимальное решение ЛП-релаксации. 2) Выбрать все множества S, для которых x S 1/f. 3) Output

f-приближение Теорема 8.1 Алгоритм «Округление ЛП-релаксации» является f- приближенным алгоритмом для задачи о покрытии. Доказательство. e U: (1) x S 1/f (e S) все элементы покрыты. Так как x S 1/f для всех выбранных S, стоимость полученного покрытия превышает стоимость дробного покрытия не больше чем в f раз.

2-приближение Следствие 8.2 Алгоритм «Округление ЛП-релаксации» является 2-приближенным алгоритмом для задачи о вершинном покрытии.

Точный пример (гиперграф) V1V1 V2V2 V3V3 VkVk V=V 1 V 2 … V k n k гиперребер Каждое гиперребро соответствует элементу, вершина – множеству (стоимость всех множеств 1), которое содержит инцидентные элементы-гиперребра.

Прямая и двойственная задачи

1-ая теорема двойственности Прямая и двойственная к ним задачи либо одновременно разрешимы, либо одновременно неразрешимы. При этом в первом случае значения целевых функций этих задач совпадают, а во втором случае, по крайней мере, одна из задач неразрешима в силу несовместности ее ограничений.

2-ая теорема двойственности Допустимые решения x и y соответственно прямой и двойственной задачи оптимальны тогда и только тогда, когда

Релаксированные условия дополняющей нежесткости Прямое условие Двойственное условие

Соотношение между целевыми функциями Утверждение 8.3 Если x и y прямое и двойственное допустимые решения, удовлетворяющие условиям дополняющей нежесткости, то

Доказательство Утверждения 8.3

ЛП-релаксация (Задача о покрытии)

Двойственная программа (Задача о покрытии)

α=1, β= f Прямое условие Двойственное условие Множество S называется строгим, если Каждый элемент имеющий ненулевое двойственное значение может быть покрыт не более f раз.

Прямо-двойственный алгоритм 0) Input (U, Ω, c: Ω Q + ) 1) x 0, y 0. 2) Until все элементы не покрыты, do Выбрать непокрытый элемент, например e, и увеличить y e до тех пор пока какое-либо множество не станет строгим. Поместить все строгие множества в покрытие и обновить x. Объявить все элементы появляющиеся в этих множествах «покрытыми». 3) Output (x)

f-приближение Теорема 8.4 Прямо-двойственный алгоритм является f-приближенным алгоритмом для задачи о покрытии.

Доказательство Теоремы 8.4 Алгоритм останавливается когда все элементы покрыты (допустимость). В покрытие выбираются только строгие множества и значения y e элементов, которые в них входят больше не изменяются (допустимость и прямое условие). Каждый элемент входит не больше чем в f множеств по условию задачи (двойственное условие). Следовательно алгоритм находит допустимое решение и по утверждению 8.3 является f-приближенным.

Точный пример 1 enen e n-1 e2e2 e1e ε e n+1 f = n

Задача «Максимальная выполнимость» Дано: Набор f дизъюнкций на булевых переменных x 1,…, x n, и веса дизъюнкций w: f Q +. Найти назначение истинности на булевых переменных, максимизирующее общий вес выполненных дизъюнкций. Дизъюнкция c выполнена, если она принимает значение «истина» (c=1).

Обозначения W – общий вес выполненных дизъюнкций. Для каждой дизъюнкции c f, случайная величина W c обозначает вес вносимый дизъюнкцией c в W.

Вероятностный алгоритм Джонсона 0) Input (x 1,…, x n, f, w: f Q + ) 1) Независимо для каждого i: x i 1 с вероятностью 0.5 и x i 0, иначе. Назовем полученное назначение τ. 3) Output (τ)

Оценка на вес дизъюнкций Для k 1, α k =1–2 –k. Лемма 8.5 Если size(c)=k, то E[W c ]=α k w c. Следствие 8.6 E[W] ½ OPT.

Вычисление условных средних Пусть a 1,…, a i будет назначение истинности на переменных x 1,…, x i. Лемма 8.7 E[W| x 1 =a 1,…, x i =a i ] может быть вычислено за время ограниченное полиномом от размера входа.

Дерандомизация Теорема 8.8 Существует такое назначение истинности x 1 =a 1,…, x n =a n, что W(a 1,…, a n ) E[W] и оно может быть вычислено за полиномиальное время.

Доказательство (индуктивный шаг) E[W| x 1 =a 1,…, x i =a i ] = E[W| x 1 =a 1,…, x i =a i, x i+1 = True]/2 + + E[W| x 1 =a 1,…, x i =a i, x i+1 = False]/2 Следовательно, либо E[W| x 1 =a 1,…, x i =a i, x i+1 = True] E[W| x 1 =a 1,…, x i =a i ], либо E[W| x 1 =a 1,…, x i =a i, x i+1 = False] E[W| x 1 =a 1,…, x i =a i ]. Выберем назначение с большим средним. Процедура требует n шагов, каждый из которых по лемме 8.7 выполняется за полиномиальное время.

Комментарий Подобная техника может быть использована и в более общем случае, даже если значения переменных зависят друг от друга. Действительно, E[W| x 1 =a 1,…, x i =a i ] = E[W| x 1 =a 1,…, x i =a i, x i+1 = True] ·Pr[x i+1 = True| x 1 =a 1,…, x i =a i ] + E[W| x 1 =a 1,…, x i =a i, x i+1 = False] ·Pr[x i+1 = False| x 1 =a 1,…, x i =a i ]. Pr[x i+1 = True| x 1 =a 1,…, x i =a i ]+Pr[x i+1 = False| x 1 =a 1,…, x i =a i ]=1. Следовательно, либо E[W| x 1 =a 1,…, x i =a i, x i+1 = True] E[W| x 1 =a 1,…, x i =a i ], либо E[W| x 1 =a 1,…, x i =a i, x i+1 = False] E[W| x 1 =a 1,…, x i =a i ].

ЦЛП задачи «Максимальная выполнимость»

ЛП задачи «Максимальная выполнимость»

Вероятностный алгоритм ЛП 0) Input (x 1,…, x n, f, w: f Q + ) 1)Решить ЛП задачи «Максимальная выполнимость». Пусть (y*, z*) обозначает оптимальное решение. 2)Независимо для каждого i: x i 1 с вероятностью y i *, и x i 0, иначе. Назовем полученное назначение τ. 3) Output (τ)

Оценка на вес дизъюнкций Для k 1, β k =1– (1 –1/k) k. Лемма 8.9 Если size(c)=k, то E[W c ] β k w c z * (c).

Доказательство

0 1 z g(z)g(z) g(z) =1– (1 – z/k) k β k =1– (1 – 1/k) k g(z)=βk·zg(z)=βk·z

1–1/e Следствие 8.10 E[W] β k OPT (если размер дизъюнкций k). Теорема 8.11 Дерандомизированный вероятностный алгоритм ЛП является (1–1/e)-приближенным алгоритмом.

Идея (¾)-приближенного алгоритма С равной вероятностью применим один из двух описанных алгоритмов. Пусть b=0, если мы применили алгоритм Джонсона и b=1, иначе. Пусть z* обозначает оптимальное решение ЛП. Лемма 8.12 E[W c ] (3/4)w c z * (c).

E[W c ] (3/4)w c z * (c) Пусть size(c)=k. Л 8.5 E[W c |b=0] = α k w c α k w c z * (c) Л 8.9 E[W c |b=1] β k w c z * (c) E[W c ] = (1/2)(E[W c |b=0]+ E[W c |b=1]) (1/2)w c z * (c)(α k +β k ) α 1 + β 1 = α 2 + β 2 = 3/2 k 3, α k + β k 7/8 + (1– 1/e) > 3/2 E[W c ] (3/4)w c z * (c)

Оценка на E[W]

Алгоритм Гоеманса-Вильямсона 0) Input (x 1,…, x n, f, w: f Q + ) 1)Решить задачу дерандомизированным вероятностным алгоритмом Джонсона. Назовем полученное назначение τ 1. 2)Решить задачу дерандомизированным вероятностным алгоритмом ЛП. Назовем полученное назначение τ 2. 4) Output (лучшее из τ 1 и τ 2 )

(3/4)-приближенный алгоритм Теорема 8.11 Алгоритм Гоеманса-Вильямсона (3/4)-приближенный алгоритм для задачи «Максимальная выполнимость».