Участник:Vlad SG

Формулировка

Пусть задана последовательность запросов к внешней памяти. Необходимо решить для каждого запроса: сохранить его значение в кэш размера [math]k[/math] или оставить его во внешней памяти.

Основные определения

Определение:

Кэш попадание (англ. cache hit) — результат обрабатываемого запроса уже хранится в кэше и его можно вернуть мгновенно. Будем считать, что время обработки такого запроса равно 0.

Определение:

Кэш промах (англ. cache miss) — результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы так же можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое. Будем считать, что время обработки такого запроса равно 1.

Определение:

Временем работы алгоритма кэширования будем называть количество кэш промахов случившихся при обработке всех запросов.

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

Определение:

Онлайн алгоритм (англ. on-line algorithm) — алгоритм, который при обработке запроса не знает следующих запросов.

Определение:

Оффлайн алгоритм (англ. off-line algorithm) — алгоритм, которому на вход даются все запросы сразу.

Определение:

[math]\alpha[/math]-оптимальность — свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в [math]\alpha[/math] раз больше, чем у любого оффлайнового, с точностью до аддитивной константы.

Ограничение детерминированных алгоритмов

Теорема:

[math]k[/math] — размер кэша. Любой [math]\alpha[/math]-оптимальный детерменированный алгоритм кэширования имеет [math]\alpha \geq k[/math].

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

[math]\triangleright[/math]

Га-га-га Теорема доказана.

[math]\triangleleft[/math]

Алгоритм

Пусть нам дан граф [math]G = \{V, E\}[/math].

int minCut(G):
  answer = [math]\infty[/math]
  for i = 1 to count
    curCut = getCut(G)
    if curCut < answer
      answer = curCut
  return answer

Так как алгоритм вероятностный и функция [math]\mathrm{getCut}[/math] возвращает вес случайного потока, а не минимального, то для того, чтобы наверняка найти вес минимального, необходим вызвать эту функцию [math]count[/math] раз. Какое конкретное значение [math]count[/math] выбрать будет описано ниже. Реализация функции [math]\mathrm{getCut}[/math] — это и есть основа алгоритма. Будем действовать следующим образом: пока вершин больше двух, будем выбирать случайное ребро и стягивать его. Когда в графе останется две вершины, то количество ребер между этими вершинами будет равно весу некоторого разреза исходного графа.

int getCut(graph):
  G = graph 
  vertexCount = количество вершин в G
  while vertexCount > 2
    edge = случайное ребро из G
    contract(edge) //стягиваем ребро edge
    vertexCount--
  edgeCount = количество ребер в G
  return edgeCount

Корректность алгоритма

Докажем корректность алгоритма. Для удобства доказательства и оценок вероятностей, будем считать, что мы ищем не просто вес минимального разреза, а величину конкретного минимального разреза. То есть зафиксируем какой-то один из минимальных разрезов, и если функция [math]\mathrm{getCut}[/math] вернет правильный вес, но посчитает его на другом минимальном разрезе, то будем считать, что ответ получен неверный. Это условие не ухудшает оценки вероятностей и время работы алгоритма.

Лемма (1):

Пусть [math]w[/math] — некоторая мультивершина, [math]u[/math] и [math]v[/math] - какие-то две из вершин, которые были стянуты в вершину [math]w[/math]. Тогда существует такой путь [math]p[/math] в исходном графе [math]G[/math] между вершинами [math]u[/math] и [math]v[/math], что ко всем ребрам этого пути была применена операция стягивания.

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

[math]\triangleright[/math]

Рассмотрим подграф [math]G'[/math] исходного графа [math]G[/math] в который входят все ребра, которые были стянуты в вершину [math]w[/math]. Очевидно, что [math]G'[/math] связен, а значит в нем существует путь между его любыми двумя вершинами. Следовательно, существует путь между [math]u[/math] и [math]v[/math], состоящий из стянутых ребер. Лемма доказана.

[math]\triangleleft[/math]

Лемма (2):

Если стянуть некоторое ребро [math]e = uv[/math] в графе G, то вес минимального разреза в графе [math]G' = G\setminus e[/math] будет не меньше чем вес минимального разреза в исходном графе [math]G[/math].

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

[math]\triangleright[/math]

Составим биекцию между ребрами графов [math]G[/math] и [math]G'[/math], не рассматривая ребра между вершинами [math]u[/math] и [math]v[/math] в графе [math]G[/math]. Очевидно, что это возможно, исходя из следующих соображений. Все ребра в [math]G[/math], не инцидентные вершинам [math]u[/math] и [math]v[/math], остались без изменений, а всем ребрам, инцидентным этим вершинам, по определению стягивания можно сопоставить новое ребро в [math]G'[/math]. Пусть [math]\langle A', B' \rangle[/math] — минимальный разрез в графе [math]G'[/math], и, не уменьшая общности, [math]w \in A'[/math]. Рассмотрим разрез [math]\langle A, B' \rangle[/math] в графе [math]G[/math]. Исходя из биекции между ребрами и тем, что все ребра вида [math]uv[/math] не пересекают разрез (так как [math]u \in A, v \in A[/math]), то [math]w(A', B') = w(A, B')[/math]. Тогда если разрез [math]\langle A, B' \rangle[/math] в графе [math]G[/math] — минимален, вес минимального разреза в [math]G'[/math] совпадает с весом минимального размера в [math]G[/math]. Если в [math]G[/math] существует разрез меньшего веса, то вес минимального разреза в [math]G'[/math] больше чем в [math]G[/math]. Лемма доказана.

[math]\triangleleft[/math]

Лемма (3):

Пусть [math]c[/math] — вес минимального потока в графе [math]G[/math]. Тогда [math]m \geqslant nc/2[/math].

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

[math]\triangleright[/math]

Заметим, что, чтобы выполнялось условие, степень каждой вершины должна быть не менее, чем [math]c[/math]. Действительно, пусть [math]\deg(v) \lt c[/math] для некоторой вершины [math]v \in V[/math]. Тогда [math]w(v, G \setminus v) = \deg(v) \lt c[/math], что противоречит условию. Далее, по лемме о рукопожатиях имеем, что [math]m \geqslant nc/2[/math]. Лемма доказана.

[math]\triangleleft[/math]

Лемма (4):

Функция [math]\mathrm{getCut}[/math] после своего выполнения получит стянутый граф [math]G'[/math] соответствующий конкретному разрезу [math]\langle A, B \rangle[/math] исходного графа [math]G[/math] тогда и только тогда, когда ни одно ребро, принадлежащее разрезу [math]\langle A, B \rangle[/math], не будет стянуто.

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

[math]\triangleright[/math]

Необходимость. От противного. Если некоторое ребро [math]uv[/math], принадлежащее разрезу [math]\langle A, B \rangle[/math] в [math]G[/math] будет стянуто, то обе вершины [math]u[/math] и [math]v[/math] будут принадлежать одной мультивершине, а значит [math]G'[/math] не соответствует разрезу [math]\langle A, B \rangle[/math]. Противоречие. Достаточность. Пусть ни одно ребро, принадлежащее разрезу [math]\langle A, B \rangle[/math] не было стянуто. Рассмотрим произвольную пару вершин [math]u \in A[/math] и [math]v \in B[/math] в графе [math]G[/math]. Если алгоритм стянул [math]u[/math] и [math]v[/math] в одну мультивершину в [math]G'[/math], тогда по лемме 1 существует путь [math]p[/math] между вершинами [math]u[/math] и [math]v[/math], и все ребра этого пути были стянуты. Но [math]p[/math] пересекает разрез [math]\langle A, B \rangle[/math], что противоречит предположению, что ни одно ребро не было стянуто. Значит, вершины из любой пары [math]u \in A[/math], и [math]v \in B[/math] были стянуты в разные мультивершины. А так, как стянутый граф состоит только из двух мультивершин, значит одна из них была получена стягиванием всех вершин из [math]A[/math], а другая — из [math]B[/math]. Лемма доказана.

[math]\triangleleft[/math]

Теорема:

Для вероятности [math]p[/math] того, что функция [math]\mathrm{getCut}[/math] после своего выполнения получит стянутый граф [math]G'[/math] соответствующий конкретному разрезу [math]\langle A, B \rangle[/math] исходного графа [math]G[/math] верна следующая оценка снизу — [math]p(\langle A, B \rangle) \geqslant[/math] [math]\frac{2}{n^2}[/math].

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

[math]\triangleright[/math]

По лемме 4 искомый стянутый граф будет получен тогда и только тогда, когда ни одно из ребер разреза не будет стянуто. Так как на каждой итерации алгоритма мы случайно выбираем ребро для стягивания, то можно оценить вероятность того, что ни одно из ребер разреза не будет стянуто. Каждое стягивание уменьшает количество ребер на [math]1[/math]. Таким образом после [math]i[/math]-ой итерации алгоритма количество вершин в текущем графе будет равно [math]n - i + 1[/math]. Рассчитаем вероятность того, что на [math]i[/math]-ой итерации будет стянуто ребро из разреза [math]\langle A, B \rangle[/math]. Пусть [math]w = w(A, B)[/math]. По лемме 2 величина минимального потока в текущем графе будет не меньше, чем [math]w[/math], и в нем будет не менее [math]\frac{w(n-i+1)}{2}[/math] вершин по лемме 3. Тогда вероятность того, что будет стянуто ребро из разреза [math]\langle A, B \rangle[/math], при условии, что до этого не было стянуто ни одно из ребер разреза, будет не более [math]\frac{2\cdot w(A,B)}{w\cdot (n-i+1)}=\frac{2}{n-i+1}.[/math] Обозначим за [math]\xi_i[/math] событие, что на [math]i[/math]-ой итерации случайным образом будет выбрано ребро из разреза [math]\langle A, B \rangle[/math]. Тогда мы только что установили, что [math]p(\xi_i | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}) \leqslant \frac{2}{n-i+1}.[/math] [math]p(\overline{\xi_i} | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}) = 1 - p(\xi_i | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}) \geqslant 1 - \frac{2}{n-i+1} = \frac{n-i-1}{n-i+1}.[/math] Тогда вероятность того, что во время работы функции не будет стянуто ни одно ребро оценивается следующим образом: [math]p(\overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{n-2}}) = \prod\limits_{i=1}^{n-2} p(\overline{\xi_i} | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}) \geqslant [/math] [math]\geqslant \prod\limits_{i=1}^{n-2} \frac{n-i-1}{n-i+1} = \frac{n - 2}{n} \cdot \frac{n-3}{n-1} \cdot \frac{n-4}{n-2} \cdot \ldots \cdot \frac{2}{4} \cdot \frac{1}{3} = \frac{2}{n(n-1)} \geqslant \frac{2}{n^2}.[/math] Теорема доказана.

[math]\triangleleft[/math]

Таким образом, мы видим, что вероятность получить правильный ответ после единичного запуска функции [math]\mathrm{getCut}[/math] очень мала. Однако, вызвав эту функцию [math]count[/math] раз мы увеличим эту вероятность. Рассчитаем значение [math]count[/math] такое, чтобы вероятность успеха была близка к [math]1[/math].

Для этого воспользуемся следующим неравенством:

[math] e^x \geqslant 1 + x[/math] для любого вещественного [math]x[/math].

Вероятность того, что мы не получим правильный ответ после [math]count[/math] независимых запусков равна

[math](1-\frac{2}{n^2})^c[/math].

Пусть [math]count = n^2\ln(n)[/math]. Тогда в силу указанного выше неравенства:

[math](1-\frac{2}{n^2})^{count} \leqslant e^{count \cdot (-\frac{2}{n^2})} = e^{-2 \ln(n)} = \frac{1}{n^2}[/math].

То есть, если вызвать функцию [math]\mathrm{getCut}[/math] [math]n^2\ln(n)[/math] раз, и после каждой итерации запоминать минимум, то вероятность того, что найденный ответ будет неверен [math] \leqslant \frac{1}{n^2}[/math]. Даже при небольших значениях [math]n[/math] алгоритм практически гарантированно выдает правильный ответ.

Оценка времени работы алгоритма

Время работы функции [math]\mathrm{getCut}[/math] — [math]O(n^2)[/math]. Функция работает [math]O(n^2\log(n))[/math] раз. Итоговое время работы — [math]O(n^4 \log(n))[/math].

Оптимизация алгоритма

Каргер совместно со Штейном (англ. Stein) придумали оптимизацию алгоритма Каргера, значительно ускоряющую время его работы. Новый алгоритм называется в честь обоих создателей — алгоритм Каргера-Штейна (англ. Karger-Stein algorithm). Его суть заключается в следуюшем. Заметим, что вероятность стягивания вершины, принадлежащей минимальному разрезу, в начале выполнения функции [math]\mathrm{getCut}[/math] довольно мала, в то время, как вероятность стянуть ребро, которое не следует стягивать, ближе к концу работы функции существенно возрастает. Тогда будем использовать следующую рекурсивную версию алгоритма:

1. Запускаем функцию [math]\mathrm{getCut}[/math] и стягиваем ребра до тех пор, пока не останется [math]\frac{n}{\sqrt{2}}[/math] вершин.
2. Запускаем независимо эту же функцию для получившегося графа дважды и возвращаем минимальный из ответов.

Такая модификация алгоритма выдает правильный ответ с точностью, не менее [math]\frac{1}{\log(n)}[/math]. Время работы функции [math]\mathrm{getCut}[/math] вычисляется рекурсивной функцией:

[math]T(n) = O(n^2) + 2 * T(n/\sqrt{2}) = O(n^2\log(n))[/math].

Это медленнее, чем оригинальный алгоритм, однако вероятность нахождения разреза минимального веса экспоненциально выше. Достаточно запустить алгоритм [math]c\log^2(n)[/math] раз, где [math]c[/math] - некоторая константа. Действительно, рассчитаем вероятность неправильного ответа также, как раньше:

[math](1-\frac{1}{log(n)})^{c\log^2(n)} \leqslant e^{c\log^2(n) \cdot -\frac{1}{log(n)}} = \frac{1}{n^c}.[/math]

Итоговое время работы — [math] O(n^2\log(n)) \cdot c\log^2(n) = O(n^2\log^3(n))[/math].

Источники

• A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, N. E. Young, Competitive Paging Algorithms, Journal of Algorithms 12, 685-699 (1991)