Примеры сетевых топологий


Метод покрытия - часть 3


2. Осуществляем выборку элементов (x,C) из U в пропорции их весов при первом розыгрыше С из С с вероятностью w(C)/w(U) и затем производим розыгрыш х путем установки хе=0, eОС, и приписав другим компонентам х значения согласно их вероятностям.

3. Вычисляем долю

, когда событие (х,С) имеет С=С(х). Тогда
(U) является несмещенной оценкой R.

Рассмотренная выше схема не является FPRAS по двум причинам. Во-первых, необходимо нумеровать все разрезы в наборе С и мощность набора растет экспоненциально с ростом объема задачи. Во-вторых, условие ограничения для w(U)/w(F) не удовлетворяется для общих случаев задачи. Карп и Луби однако, модифицировали процедуру, описанную выше, для случая задач надежности (s,t)-связности, где граф G является плоским и однонаправленным и ограничения сопряжены с множественностью и суммарной вероятностью, а также выполняется условие ограничения сверху ПeО С(1+qe) некоторым фиксированным М.

Мы здесь не вдаемся в детали, главная идея заключается в расширении С, чтобы включить разрезы, которые являются “почти минимальными”, таким образом, чтобы ассоциированное пространство U, определенное выше, удовлетворяло требуемым свойствам с учетом F. Плоскость G используется, чтобы разрешить эффективную выборку элементов расширенного пространства U с правильными вероятностями, так чтобы модифицированная схема для задач надежности (s,t)-связности стала FPRAS.




Начало  Назад  Вперед