Случайное округление - Википедия - Randomized rounding

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

В Информатика и исследование операций,много комбинаторная оптимизация проблемы вычислительно несговорчивый решать точно (до оптимальности). Многие такие задачи решаются быстро (полиномиальное время ) аппроксимационные алгоритмы - то есть алгоритмы, которые гарантированно возвращают приблизительно оптимальное решение при любом вводе.

Рандомизированное округление(Рагхаван и Томпсон 1987 ) является широко используемым подходом для проектирования и анализа таких аппроксимационные алгоритмы.^[1][2] Основная идея - использовать вероятностный метод преобразовать оптимальное решение расслабление проблемы в приблизительно оптимальное решение исходной задачи.

Обзор

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

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

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

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

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

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

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

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

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

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

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

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

Установить пример обложки

В следующем примере показано, как можно использовать рандомизированное округление для разработки алгоритма аппроксимации для Установить обложку проблема.

Исправить любой экземпляр ${ displaystyle langle c, { mathcal {S}} rangle}$ набора обложки над вселенной ${ displaystyle { mathcal {U}}}$.

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

Для шага 2 пусть LP будет релаксация линейного программирования IP и вычислить оптимальное решение ${ displaystyle x ^ {*}}$ к LP с использованием любого стандарта линейное программирование алгоритм (для этого требуется время, полиномиальное от входного размера).

(Возможные решения LP - это векторы ${ displaystyle x}$которые назначают каждый набор ${ displaystyle s in { mathcal {S}}}$неотрицательный вес ${ displaystyle x_ {s}}$, так что для каждого элемента ${ displaystyle е in { mathcal {U}}}$,${ displaystyle x '}$ охватывает ${ displaystyle e}$- общий вес наборов, содержащих ${ displaystyle e}$не меньше 1, то есть

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

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

${ Displaystyle сумма _ {s in { mathcal {S}}} с (S) x_ {s} ^ {*}}$

как можно меньше.)

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

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

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

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

Шаг 3. Шаг рандомизированного округления

Вот описание третьего шага - шага округления, который должен преобразовать минимальную стоимость дробного покрытия набора ${ displaystyle x ^ {*}}$в допустимое целочисленное решение ${ displaystyle x '}$ (соответствует истинной обложке набора).

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

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

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

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

${ Displaystyle prod _ {s ni e} 1-x_ {s} ^ {*} приблизительно prod _ {s ni e} exp (-x_ {s} ^ {*}) = exp { Big (} - sum _ {s ni e} x_ {s} ^ {*} { Big)} приблизительно exp (-1).}$

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

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

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

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

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

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

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

(Примечание: осторожно ${ Displaystyle О ( журнал | { mathcal {U}} |)}$можно свести к ${ displaystyle ln (| { mathcal {U}} |) + O ( log log | { mathcal {U}} |)}$.)

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

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

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

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

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

${ Displaystyle { begin {align} 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 {выравнивается}}}$

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

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

Посредством наивный союз, вероятность того, что один из ${ displaystyle 1+ | { mathcal {U}} |}$ плохие события случаются меньше чем ${ Displaystyle 1/2 + | { mathcal {U}} | / (2 { mathcal {U}}) = 1}$Таким образом, с положительной вероятностью не бывает плохих событий и ${ displaystyle x '}$ это набор покрытия расходов на максимум ${ Displaystyle 2 лямбда с cdot x ^ {*}}$.QED

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

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

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

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

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

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

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

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

куда

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

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

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

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

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

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

${ displaystyle 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}).}$

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

Удержание условной вероятности отказа ниже 1

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

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

(куда ${ displaystyle m = | { mathcal {S}} |}$).

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

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

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

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

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

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

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

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

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

Алгоритм случайного округления для набора покрытий

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

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

1. Вычислить минимальную стоимость частичного покрытия набора ${ displaystyle x ^ {*}}$ (оптимальное решение релаксации ЛП).
2. Позволять ${ Displaystyle лямбда leftarrow ln (2 | { mathcal {U}} |)}$. Позволять ${ displaystyle p_ {s} leftarrow min ( lambda x_ {s} ^ {*}, 1)}$ для каждого ${ displaystyle s in { mathcal {S}}}$.
3. Для каждого ${ displaystyle s ' in { mathcal {S}}}$ делать:
   1. Позволять ${ Displaystyle { mathcal {S}} leftarrow { mathcal {S}} - {s '}}$.   (${ Displaystyle { mathcal {S}}}$ содержит еще не определенные наборы.)
   2. Если ${ displaystyle { 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})}$

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

      еще набор ${ displaystyle x '_ {s} leftarrow 1}$ и ${ displaystyle { mathcal {U}} leftarrow { mathcal {U}} - s '}$.

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

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

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

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

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

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

Замечания

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

Смотрите также

• Метод условных вероятностей

Рекомендации

• Рагхаван, Прабхакар; Томпсон, Кларк Д. (1987), «Рандомизированное округление: метод доказуемо хороших алгоритмов и алгоритмических доказательств», Комбинаторика, 7 (4): 365–374, Дои:10.1007 / BF02579324, S2CID  5749936.
• Рагхаван, Прабхакар (1988), «Вероятностное построение детерминированных алгоритмов: аппроксимация упаковки целочисленных программ», Журнал компьютерных и системных наук, 37 (2): 130–143, Дои:10.1016/0022-0000(88)90003-7.

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

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