1 Комбинаторные алгоритмы Задача о k-центрах

2 Метрическая задача o k центрах Дано: Полный граф G = (V, E), стоимости ребер cost: E Q + такие, что для любых трех вершин u, v и w: cost(u,v) cost(u,w) + cost(w,v). Для любого множества S V, определим connect(v,S) = min{cost(u,v)|u S}. Найти множество S V, с |S|=k, которое минимизирует величину max v {connect(v,S)}. Метрическая задача o k центрах – NP-трудна.

3 Пример 10753

4 Идея алгоритма (k=2, OPT 7) 10753

5 Идея алгоритма (k=2, OPT 3) 10753

6 Параметрическое сокращение Упорядочим ребра в G по невозрастанию их стоимости cost(e 1 ) cost(e 2 ) … cost(e m ). Пусть G i = (V, E i ), где E i ={e 1, e 2,…, e i }. Для каждого G i, нужно проверить существует ли множество S V, с которым смежна каждая вершина из V – S.

7 Доминирующее множество Доминирующим множеством в графе G = (V, E) называется подмножество вершин S V такое, что каждая вершина в V – S смежна некоторой вершине в S. dom(G) – размер доминирующего множества минимальной мощности. Вычисление dom(G) – NP-трудная задача.

8 Задача o k центрах Задача o k центрах эквивалентна задаче нахождения наименьшего индекса i такого, что G i имеет доминирующее множество размера k. G i содержит k звезд (K 1,p ), которые охватывают все вершины. K 1,7

9 G2G2 Независимым множеством в графе G = (V, E) называется подмножество вершин I V такое, что в нем нет смежных вершин. Квадратом графа G = (V, E) называется граф G 2 = (V, E), где (u,v) E, когда длина пути между вершинами u и v меньше или равна 2. G=K 1,4 G2=K5G2=K5

10 Нижняя оценка Лемма 6.1 Дан граф H, пусть I будет независимое множество в H 2. Тогда | I | dom(H).

11 Алгоритм Хошбаум-Шмойса Input (G, cost: E Q + ) 1) Строим G 1 2, G 2 2,…, G m 2. 2) Найти максимальное независимое множество I r в каждом графе G r 2. 3)Вычислить наименьший индекс r такой, что | I r | k. Пусть это будет j. Output (I j )

12 Оценка качества алгоритма Хошбаум-Шмойса Теорема 6.2 Алгоритм Хошбаум-Шмойса является 2-приближенным алгоритмом для метрической задачи o k центрах.

13 Ключевая лемма Лемма 6.3 Для j, определенного алгоритмом, cost(e j ) OPT. Доказательство. Для каждого r k. Тогда по лемме 6.1 dom(G r ) | I r | > k. Поэтому r* > r, и r* j. cost(e j ) OPT

14 Доказательство Теоремы 6.2 Максимальное независимое множество является также и доминирующим. В графе G j 2 найдутся звезды с центрами в вершинах I j, которые покрывают все вершины G. Из неравенства треугольника стоимость ребер в G j 2 не превосходит 2cost(e j ). По лемме 6.3: 2 cost(e j ) 2 OPT.

15 Точность оценки

16 Метрическая задача o взвешенных центрах Дано: Полный граф G = (V, E), стоимости ребер cost: E Q + такие, что для любых трех вершин u, v и w: cost(u,v) cost(u,w) + cost(w,v) и w: V R +, и граница W R +. Найти множество S V, суммарного веса не больше W, которое минимизирует величину max v {connect(v,S)}.

17 Взвешенное доминирующее множество Доминирующим множеством в графе G = (V, E) называется подмножество вершин S V такое, что каждая вершина в V – S смежна некоторой вершине в S. wdom(G) – вес доминирующего множества минимального веса в G. Вычисление wdom(G) – NP-трудная задача.

18 Параметрическое сокращение Упорядочим ребра в G по невозрастанию их стоимости cost(e 1 ) cost(e 2 ) … cost(e m ). Пусть G i = (V, E i ), где E i ={e 1, e 2,…, e i }. Требуется найти наименьший индекс i такой, что G i имеет доминирующее множество веса не больше W, то есть wdom(G i ) W.

19 Лёгкие соседи Расстоянием (dist(v,u), dist G (v,u) ) для двух вершин v и u называется длина кратчайшего v-u-пути в G. Neighbor G (u) = {v| dist G (u,v) 1} Дан граф G = (V, E), и w: V R +, пусть I будет независимое множество в G 2. Пусть s(u) Neighbor G (u) обозначает соседа u в G наименьшего веса. S = {s(u) | u I }

20 Нижняя оценка Лемма 6.4 Дан граф H, пусть I будет независимое множество в H 2. Тогда w(S) wdom(H). Доказательство. Пусть D доминирующее множество минимального веса в H. Тогда набор непересекающихся звезд в H с центрами в D и покрывающими все вершины. Так как, каждая звезда превращается в клику в H 2, то в I попадет не более одной вершины из такой клики. Каждая попавшая вершина является в исходном графе соседом центра из D w(S) wdom(H).

21 Алгоритм Хошбаум-Шмойса-2 Input (G, cost: E Q +, w: V R +,W) 1) Построить G 1 2, G 2 2,…, G m 2. 2) Найти максимальное независимое множество I r в каждом графе G r 2. 3) Построить S r = {s r (u) | u I r } 4) Вычислить наименьший индекс r такой, что w(S r ) W. Пусть это будет j. Output (S j )

22 Оценка качества алгоритма Хошбаум-Шмойса-2 Теорема 6.5 Алгоритм Хошбаум-Шмойса является 3-приближенным алгоритмом для метрической задачи o k взвешенных центрах.

23 Точность оценки 22 1+ε ε 11 1 G b a cd

24 Точность оценки 22 1+ε ε 11 1 G 2 I n+3 ={b} b a cd S n+3 ={a}OPT={a, c}

25 Задача «Кратчайшая суперстрока» Дано: Конечный алфавит Σ и множество из n строк S = {s 1,…,s n } Σ +. Найти кратчайшую суперстроку s, которая содержит каждую строку s i, как подстроку. Без ограничения общности будем считать, что никакая строка s i не содержит другую строку s j, i j, как подстроку.

26 Сумма префиксов s s1s1 s n–1 s2s2 pref(s 1, s 2 ) snsn s1s1 pref(s n–1, s n )pref(s n, s 1 )over(s n, s 1 )

27 Ориентированный граф префиксов G pref = (V, A) – полный орграф. V={s 1,…,s n }={1,…,n} дуга (s i, s j ) имеет вес prefix(s i,s j ). | prefix(s 1,s 2 )| + | prefix(s 2,s 3 )| + …+ | prefix(s n,s 1 )| – вес тура s 1 s 2 … s n s 1 (1 2 … n 1). Минимальный по весу гамильтонов цикл – нижняя оценка на длину кратчайшей суперстроки s.

28 Нижняя оценка Циклическое покрытие – набор непересекающихся циклов, покрывающих все вершины. Гамильтонов цикл также является циклическим покрытием. Циклическое покрытие минимального веса – нижняя оценка на длину кратчайшей суперстроки. Циклическое покрытие минимального веса можно вычислить за полиномиальное время.

29 От цикла к префиксам Если c = (i 1 i 2 … i l i 1 ) – цикл в префиксном графе, то α(с) = prefix(s i 1,s i 2 ) … prefix(s i l-1,s i l ) prefix(s i l,s i 1 ). α(с) – вес цикла с. Каждая из строк s i 1,s i 2,…, s i l – это подстрока в (α(с)). σ(с) = α(с) s i 1. σ(с) – суперстрока над s i 1,s i 2,…, s i l. s i 1 – первая строка в цикле с.

30 Пример abcdeabcdeabcde bcdeabcdeabcdea cdeabcdeabcdeabc deabcdeabcdeabcd abcdeabcdeabcde α(с)=abcde, (α(с)) 2 =abcdeabcde, bcdeabcdeabcdea – подстрока (α(с)) 4. σ(с) = abcdeabcdeabcdeabcde

31 Алгоритм «Суперстрока» Input (s 1,…,s n ) 1) Построить префиксный граф G pref для s 1,…,s n. С 2) Найти минимальное по весу циклическое покрытие G pref, С = {c 1,…,c k } Output (σ(c 1 ) … σ(c k )).

32 Замечание Очевидно, что σ(c 1 ) … σ(c k ) является суперстрокой. Более того, если в каждом цикле есть строка, длина которой не превосходит вес цикла, то решение не превосходит 2OPT. Таким образом решение может быть плохим, если все строки в цикле длинные.

33 Оценка веса покрывающего цикла Лемма 6.6 Если каждая строка в S S является подстрочкой t для строки t, то существует цикл веса не больше t в префиксном графе, покрывающий все вершины, соответствующие строкам в S.

34 Доказательство леммы 6.6 Упорядочим строки из S по моментам их первого появления в t. Все эти моменты различны и появляются в первой копии t. Рассмотрим цикл в префиксном графе, посещающий вершины в заданном порядке. Ясно, что его вес не больше чем t.

35 Оценка мощности пересечения двух первых строк Лемма 6.7 Пусть c и c два цикла в C (циклическое покрытие минимального веса), и пусть r, r первые строки этих циклов. Тогда |overlap(r, r)| < w(c) + w(c).

36 |overlap(r, r)| w(c) + w(c). r r'r' overlap(r, r) αα α'α'α'α' α'α' α α' = α' α α – префикс длины w(c) в пересечении r и r. (α) = (α') цикл длины w(c) в префиксном графе, покрывающем все строки в c и c.

37 Оценка качества алгоритма «Суперстрока» Теорема 6.8 Алгоритм «Суперстрока» является 4-приближенным алгоритмом для задачи «Кратчайшая суперстрока».

38 Доказательство r i – первая строка в с i.