Рандомизированное округление

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

Многие комбинаторной оптимизации задачи невозможно решить точно (до оптимальности) вычислительно. Для таких задач рандомизированное округление может использоваться для разработки быстрых ( полиномиальных ) алгоритмов аппроксимации , то есть алгоритмов, которые гарантированно возвращают приблизительно оптимальное решение при любых входных данных.

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

Обзор

Базовый подход состоит из трех этапов:

1. Сформулируйте решаемую задачу в виде целочисленной линейной программы (ЦЛП).
2. Вычислите оптимальное дробное решение $x$ к релаксации линейного программирования (LP) ILP.
3. Округляем дробное решение $x$ ЛП к целочисленному решению $x'$ НЛП.

(Хотя этот подход чаще всего применяется к линейным программам,иногда используются и другие виды релаксации.Например, см. полуопределенном программировании основанное на Гоеманса и Уильямсона Алгоритм аппроксимации Max-Cut .)

На первом этапе задача состоит в том, чтобы выбрать подходящую целочисленную линейную программу.Требуется знание линейного программирования, в частности моделирования с использованием линейных программ и целочисленных линейных программ. Для многих задач существует естественная целочисленная линейная программа, которая хорошо работает:например, в примере «Установить обложку» ниже. (Целочисленная линейная программа должна иметь небольшой разрыв целостности ;действительно, рандомизированное округление часто используется для доказательства границ пробелов в целочисленности.)

На втором этапе обычно можно вычислить оптимальное дробное решение.за полиномиальное время используя любой стандартный алгоритм линейного программирования .

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

Основным методом выполнения третьего шага (округления) является использование рандомизации.а затем использовать вероятностные аргументы, чтобы ограничить увеличение затрат из-за округления(следуя вероятностному методу комбинаторики).Здесь с помощью вероятностных аргументов показано существование дискретных структур сжелаемые свойства. В этом контексте такие аргументы используются, чтобы показать следующее:

Учитывая любое дробное решение $x$ LP, с положительной вероятностью процесс рандомизированного округления дает целочисленное решение $x'$ что приближает $x$ по какому-то желаемому критерию.

Наконец, чтобы сделать третий шаг вычислительно эффективным,либо это показывает $x'$ приближает $x$с высокой вероятностью (чтобы шаг мог оставаться рандомизированным)или можно дерандомизировать шаг округления,обычно используют метод условных вероятностей .Последний метод преобразует процесс рандомизированного округленияв эффективный детерминированный процесс, который гарантировандля достижения хорошего результата.

Пример: задача о наборе покрытия

Следующий пример иллюстрирует, как можно использовать рандомизированное округление для разработки аппроксимационного алгоритма для задачи покрытия множеств . Исправьте любой экземпляр $\langle c,{\mathcal {S}}\rangle$ установить покров над вселенной ${\mathcal {U}}$.

Вычисление дробного решения

Для шага 1 пусть IP будет стандартной целочисленной линейной программой для покрытия множества для этого экземпляра.

Для шага 2 пусть LP будет релаксацией линейного программирования IP и вычислит оптимальное решение. $x^{*}$ в LP с использованием любого стандартного алгоритма линейного программирования . Это требует полинома времени от входного размера. Допустимыми решениями задачи LP являются векторы $x$ которые назначают каждый набор $s\in {\mathcal {S}}$ неотрицательный вес $x_{s}$, такой, что для каждого элемента $e\in {\mathcal {U}}$, $x'$ обложки $e$— общий вес, присвоенный наборам, содержащим $e$ не менее 1, то есть

$\sum _{s\ni e}x_{s}\geq 1.$

Оптимальное решение $x^{*}$ является возможным решением, стоимость которого

$\sum _{s\in {\mathcal {S}}}c(S)x_{s}^{*}$

как можно меньше. Обратите внимание, что любая обложка комплекта ${\mathcal {C}}$ для ${\mathcal {S}}$ дает возможное решение $x$ (где $x_{s}=1$ для $s\in {\mathcal {C}}$, $x_{s}=0$ в противном случае). Стоимость этого ${\mathcal {C}}$ равна стоимости $x$, то есть,

$\sum _{s\in {\mathcal {C}}}c(s)=\sum _{s\in {\mathcal {S}}}c(s)x_{s}.$

Другими словами, линейная программа LP является релаксацией данной задачи покрытия множеств.

С $x^{*}$ имеет минимальную стоимость среди возможных решений ЛП, стоимость $x^{*}$ — нижняя граница стоимости покрытия оптимального множества .

Случайный шаг округления

На шаге 3 мы должны преобразовать покрытие дробного множества с минимальной стоимостью $x^{*}$ в допустимое целочисленное решение $x'$ (соответствует настоящей обложке комплекта). Шаг округления должен дать $x'$ который с положительной вероятностью имеет стоимость в пределах небольшого коэффициента стоимости $x^{*}$.Тогда (поскольку стоимость $x^{*}$ — нижняя граница стоимости покрытия оптимального множества), стоимость $x'$ будет в пределах небольшого коэффициента оптимальной стоимости.

В качестве отправной точки рассмотрим наиболее естественную схему округления:

Для каждого набора $s\in {\mathcal {S}}$ в свою очередь, возьмите $x'_{s}=1$ с вероятностью $\min(1,x_{s}^{*})$, иначе возьмем $x'_{s}=0$.

При такой схеме округления ожидаемая стоимость выбранных наборов не превышает $\sum _{s}c(s)x_{s}^{*}$, стоимость дробного покрытия. Это хорошо. К сожалению, покрытие не очень хорошее. Когда переменные $x_{s}^{*}$ малы, вероятность того, что элемент $e$ не охвачено

$\prod _{s\ni e}1-x_{s}^{*}\approx \prod _{s\ni e}\exp(-x_{s}^{*})=\exp {\Big (}-\sum _{s\ni e}x_{s}^{*}{\Big )}\approx \exp(-1).$

Таким образом, в ожидании будет охвачена только постоянная доля элементов.

Сделать $x'$ покрыть каждый элемент с высокой вероятностью, стандартная схема округления сначала увеличивает вероятности округления на соответствующий коэффициент $\lambda >1$. Вот стандартная схема округления:

Исправить параметр $\lambda \geq 1$. Для каждого набора $s\in {\mathcal {S}}$ по очереди,

брать $x'_{s}=1$ с вероятностью $\min(\lambda x_{s}^{*},1)$, иначе возьмем $x'_{s}=0$.

Увеличение вероятностей на $\lambda$ увеличивает ожидаемую стоимость на $\lambda$, но делает вероятным охват всех элементов. Идея состоит в том, чтобы выбрать $\lambda$ как можно меньше, чтобы все элементы были доказуемо покрыты с ненулевой вероятностью. Вот подробный анализ.

---

Лемма (гарантия аппроксимации для схемы округления)

Исправить $\lambda =\ln(2|{\mathcal {U}}|)$. С положительной вероятностью схема округления возвращает заданное покрытие $x'$ стоимость максимум $2\ln(2|{\mathcal {U}}|)c\cdot x^{*}$ (и, следовательно, стоимость $O(\log |{\mathcal {U}}|)$ раз превышает стоимость оптимального комплекта покрытия).

(Примечание: с осторожностью $O(\log |{\mathcal {U}}|)$ можно свести к $\ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)$.)

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

Выход $x'$ схемы случайного округления обладает желаемыми свойствамидо тех пор, пока не произойдет ни одно из следующих «плохих» событий:

1. стоимость $c\cdot x'$ из $x'$ превышает $2\lambda c\cdot x^{*}$, или
2. для какого-то элемента $e$, $x'$ не в состоянии покрыть $e$.

Ожидание каждого $x'_{s}$ самое большее $\lambda x_{s}^{*}$. Ввиду линейности ожидания ожидание $c\cdot x'$самое большее $\sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}$. Таким образом, по неравенству Маркова вероятность первого плохого событиявыше это самое большее $1/2$.

Для остальных плохих событий (по одному на каждый элемент $e$), Обратите внимание, что,с $\sum _{s\ni e}x_{s}^{*}\geq 1$ для любого заданного элемента $e$, вероятность того, что $e$ не покрыт

${\begin{aligned}\prod _{s\ni e}{\big (}1-\min(\lambda x_{s}^{*},1){\big )}&<\prod _{s\ni e}\exp({-}\lambda x_{s}^{*})=\exp {\Big (}{-}\lambda \sum _{s\ni e}x_{s}^{*}{\Big )}\\&\leq \exp({-}\lambda )=1/(2|{\mathcal {U}}|).\end{aligned}}$

(При этом используется неравенство $1+z\leq e^{z}$, что является строгим для $z\neq 0$.)

Таким образом, для каждого из $|{\mathcal {U}}|$ элементы,вероятность того, что элемент не покрыт, меньше $1/(2{\mathcal {U}})$.

По границе объединения вероятность того, что один из $1+|{\mathcal {U}}|$ происходят плохие событияменьше, чем $1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1$.Таким образом, при положительной вероятности плохих событий не бывает.и $x'$ не более чем установленное покрытие затрат $2\lambda c\cdot x^{*}$. ЯВЛЯЕТСЯ

Дерандомизация с использованием метода условных вероятностей

Приведенная выше лемма показывает существование множества покрытий затрат. $O(\log(|{\mathcal {U}}|)c\cdot x^{*}$).В этом контексте нашей целью является эффективный алгоритм аппроксимации,это не просто доказательство существования, так что мы еще не закончили.

Одним из подходов было бы увеличение $\lambda$немного, а затем покажите, что вероятность успеха равна, скажем, не менее 1/4.С этой модификацией повторение шага случайного округления несколько раздостаточно, чтобы обеспечить успешный результат с высокой вероятностью.

Такой подход ослабляет коэффициент аппроксимации.Далее мы опишем другой подход, который даетдетерминированный алгоритм, который гарантированносоответствовать коэффициенту аппроксимации приведенного выше доказательства существования.Этот подход называется методом условных вероятностей .

Детерминированный алгоритм имитирует схему рандомизированного округления:он рассматривает каждый набор $s\in {\mathcal {S}}$ по очереди,и выбирает $x'_{s}\in \{0,1\}$.Но вместо того, чтобы делать каждый выбор случайным образом на основе $x^{*}$,он делает выбор детерминированно , чтобы сохранить условную вероятность неудачи, учитывая выбор на данный момент, ниже 1 .

Ограничение условной вероятности отказа

Мы хотим иметь возможность устанавливать каждую переменную $x'_{s}$ по очередитак, чтобы условная вероятность отказа была ниже 1.Для этого нам нужна хорошая оценка условной вероятности отказа.Граница будет достигнута путем уточнения исходного доказательства существования.Это доказательство неявно ограничивает вероятность неудачи.по математическому ожиданию случайной величины

$F={\frac {c\cdot x'}{2\lambda c\cdot x^{*}}}+|{\mathcal {U}}^{(m)}|$,

где

${\mathcal {U}}^{(m)}={\Big \{}e:\prod _{s\ni e}(1-x'_{s})=1{\Big \}}$

— это набор элементов, оставшихся непокрытыми в конце.

Случайная величина $F$ может показаться немного загадочным,но оно систематически отражает вероятностное доказательство.Первый срок в $F$ получается в результате применения неравенства Маркова ограничить вероятность первого плохого события (цена слишком высока).Это способствует как минимум 1 $F$ если стоимость $x'$ слишком высок.Второй срокподсчитывает количество плохих событий второго рода (неохваченных элементов).Это способствует как минимум 1 $F$ если $x'$ оставляет любой элемент непокрытым.Таким образом, при любом исходе, когда $F$ меньше 1, $x'$ должен охватывать все элементыи стоим, достигая желаемой границы из леммы.Короче говоря, если этап округления не удался, то $F\geq 1$.Отсюда следует (по неравенству Маркова ), что $E[F]$ является верхней границей вероятности отказа. Заметим, что приведенное выше рассуждение неявно присутствует уже в доказательстве леммы:что также показывает расчетным путем, что $E[F]<1$.

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

Итак, как насчет условной вероятности неудачи при переборе наборов на этапе округления?С $F\geq 1$ в любом результате, когда этап округления не удался,по неравенству Маркова условная вероятность отказав лучшем случае является условным ожиданием $F$.

Далее вычисляем условное математическое ожидание $F$,так же, как мы рассчитали безусловное ожидание $F$ в оригинальном доказательстве.Рассмотрим состояние процесса округления в конце некоторой итерации $t$.Позволять $S^{(t)}$ обозначаем множества, рассмотренные до сих пор(первый $t$ наступает ${\mathcal {S}}$).Позволять $x^{(t)}$ обозначим (частично присвоенный) вектор $x'$(так $x_{s}^{(t)}$ определяется только в том случае, если $s\in S^{(t)}$).Для каждого набора $s\not \in S^{(t)}$,позволять $p_{s}=\min(\lambda x_{s}^{*},1)$обозначают вероятность, с которой $x'_{s}$ будет установлено на 1.Позволять ${\mathcal {U}}^{(t)}$ содержат еще не рассмотренные элементы.Тогда условное ожидание $F$,учитывая выбор, сделанный до сих пор, то есть учитывая $x^{(t)}$, является

$E[F|x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)}}c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).$

Обратите внимание, что $E[F|x^{(t)}]$ определяется только после итерации $t$.

Сохранение условной вероятности отказа ниже 1.

Чтобы условная вероятность отказа была ниже 1,достаточно сохранить условное ожидание $F$ ниже 1.Для этого достаточно сохранить условное математическое ожидание $F$ от увеличения.Это то, что будет делать алгоритм.Это установит $x'_{s}$ на каждой итерации, чтобы гарантировать, что

$E[F|x^{(m)}]\leq E[F|x^{(m-1)}]\leq \cdots \leq E[F|x^{(1)}]\leq E[F|x^{(0)}]<1$

(где $m=|{\mathcal {S}}|$).

В $t$итерация,как можно задать алгоритм $x'_{s'}$чтобы гарантировать, что $E[F|x^{(t)}]\leq E[F|S^{(t-1)}]$?Оказывается, он может просто установить $x'_{s'}$так, чтобы минимизировать результирующее значение $E[F|x^{(t)}]$.

Чтобы понять почему, сосредоточимся на моменте времени, когда итерация $t$ начинается.В это время, $E[F|x^{(t-1)}]$ определяется,но $E[F|x^{(t)}]$ еще не определено--- оно может принимать два возможных значения в зависимости от того, как $x'_{s'}$устанавливается в итерации $t$.Позволять $E^{(t-1)}$ обозначаем значение $E[F|x'^{(t-1)}]$.Позволять $E_{0}^{(t)}$ и $E_{1}^{(t)}$,обозначаем два возможных значения $E[F|x^{(t)}]$,в зависимости от того, $x'_{s'}$ устанавливается в 0 или 1 соответственно.По определению условного ожидания,

$E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{(t)}+\Pr[x'_{s'}=1]E_{1}^{(t)}.$

Поскольку средневзвешенное значение двух величинвсегда является минимумом из этих двух величин,отсюда следует, что

$E^{(t-1)}~\geq ~\min(E_{0}^{(t)},E_{1}^{(t)}).$

Таким образом, постановка $x'_{s'}$так, чтобы минимизировать результирующее значение $E[F|x^{(t)}]$будет гарантировать, что $E[F|x^{(t)}]\leq E[F|x^{(t-1)}]$.Это то, что будет делать алгоритм.

Подробно, что это значит?Рассматривается как функция $x'_{s'}$(при всех остальных количествах фиксированных) $E[F|x^{(t)}]$является линейной функцией $x'_{s'}$,и коэффициент $x'_{s'}$ в этой функции есть

${\frac {c_{s'}}{2\lambda c\cdot x^{*}}}~-~\sum _{e\in s'\cap {\mathcal {U}}_{t-1}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).$

Таким образом, алгоритм должен задать $x'_{s'}$ до 0, если это выражение положительное,и 1 в противном случае. Это дает следующий алгоритм.

Алгоритм рандомизированного округления для покрытия множества

ввод: установить систему ${\mathcal {S}}$, вселенная ${\mathcal {U}}$, вектор стоимости $c$

вывод: установить обложку $x'$ (решение стандартной целочисленной линейной программы для покрытия множеств)

1. Вычислить покрытие дробного множества минимальной стоимости $x^{*}$ (оптимальное решение проблемы релаксации ЛП).
2. Позволять $\lambda \leftarrow \ln(2|{\mathcal {U}}|)$. Позволять $p_{s}\leftarrow \min(\lambda x_{s}^{*},1)$ для каждого $s\in {\mathcal {S}}$.
3. Для каждого $s'\in {\mathcal {S}}$ делать:
   1. Позволять ${\mathcal {S}}\leftarrow {\mathcal {S}}-\{s'\}$.   ( ${\mathcal {S}}$ содержит еще не определенные наборы.)
   2. Если ${\frac {c_{s'}}{2\lambda c\cdot x^{*}}}>\sum _{e\in s'\cap {\mathcal {U}}}\prod _{s\in {\mathcal {S}},s\ni e}(1-p_{s})$

      затем установите $x'_{s}\leftarrow 0$,

      еще установить $x'_{s}\leftarrow 1$ и ${\mathcal {U}}\leftarrow {\mathcal {U}}-s'$.

        ( ${\mathcal {U}}$ содержит еще не рассмотренные элементы.)

4. Возвращаться $x'$.

лемма (гарантия аппроксимации алгоритма)

Приведенный выше алгоритм возвращает заданное покрытие $x'$ стоимость максимум $2\ln(2|{\mathcal {U}}|)$ раз минимальная стоимость любого (дробного) покрытия комплекта.

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

Алгоритм гарантирует, что условное ожидание $F$, $E[F\,|\,x^{(t)}]$, не увеличивается на каждой итерации.Поскольку это условное ожидание изначально меньше 1 (как показано ранее),алгоритм гарантирует, что условное ожидание остается ниже 1.Поскольку условная вероятность отказав лучшем случае является условным ожиданием $F$,таким образом алгоритмгарантирует, что условная вероятность отказа остается ниже 1.Таким образом, в конце, когда все варианты выбора определены,алгоритм достигает успешного результата.То есть алгоритм выше возвращает множество покрытий $x'$стоимость максимум $2\ln(2|{\mathcal {U}}|)$ разминимальная стоимость любого (дробного) комплекта покрытия.

Примечания

В приведенном выше примере алгоритм руководствовался условным ожиданием случайной величины $F$.В некоторых случаях вместо точного условного ожидания используется верхняя (а иногда и нижняя) граница.вместо этого используется некоторое условное ожидание. Это называется пессимистической оценкой .

Сравнение с другими приложениями вероятностного метода

Шаг рандомизированного округления отличается от большинства применений вероятностного метода в двух отношениях:

1. этапа Важна вычислительная сложность округления. Это должно быть реализовано с помощью быстрого (например, полиномиального ) алгоритма .
2. Распределение вероятностей, лежащее в основе случайного эксперимента, является функцией решения $x$ релаксации . проблемного экземпляра Этот факт имеет решающее значение для доказательства гарантии производительности алгоритма аппроксимации, то есть того, что для любого экземпляра задачи алгоритм возвращает решение, которое аппроксимирует оптимальное решение для этого конкретного экземпляра . Для сравнения, приложения вероятностного метода в комбинаторике обычно показывают существование структур, характеристики которых зависят от других входных параметров. Например, рассмотрим теорему Турана , которую можно сформулировать как «любой граф с $n$ вершины средней степени $d$ должен иметь независимый набор размеров как минимум $n/(d+1)$. (См. здесь вероятностное доказательство теоремы Турана .) Хотя существуют графы, для которых эта граница точна, есть также графы, которые имеют независимые множества, намного большие, чем $n/(d+1)$. Таким образом, размер независимого множества, существование которого в графе согласно теореме Турана показано в соответствии с теоремой Турана, в общем случае может быть намного меньше, чем максимальное независимое множество для этого графа.

См. также

• Метод условных вероятностей
• Рандомизированное округление без решения линейной программы.

Ссылки

• Рагхаван, Прабхакар (1988), «Вероятностное построение детерминированных алгоритмов: аппроксимация программ упаковки целых чисел», Journal of Computer and System Sciences , 37 (2): 130–143, doi : 10.1016/0022-0000(88)90003-7 .

Дальнейшее чтение

• Альтёфер, Инго (1994), «О редких приближениях к рандомизированным стратегиям и выпуклым комбинациям», Линейная алгебра и ее приложения , 199 : 339–355, doi : 10.1016/0024-3795(94)90357-3 , MR   1274423
• Хофмайстер, Томас; Лефманн, Ханно (1996), «Детерминированное вычисление разреженных приближений», Линейная алгебра и ее приложения , 240 : 9–19, doi : 10.1016/0024-3795(94)00175-8 , MR   1387283
• Липтон, Ричард Дж.; Янг, Нил Э. (1994), «Простые стратегии для больших игр с нулевой суммой с приложениями к теории сложности», STOC '94: Материалы двадцать шестого ежегодного симпозиума ACM по теории вычислений , Нью-Йорк, Нью-Йорк: ACM , стр. 734–740, arXiv : cs.cc/0205035 , doi : 10.1145/195058.195447 , ISBN.  978-0-89791-663-9 , S2CID   7524887