В области компьютерных наук и исследований операций многие задачи комбинаторной оптимизации сложно решить с помощью вычислений точно (до оптимальности). Многие из таких задач допускают быстрые ( полиномиальное время ) алгоритмы аппроксимации, то есть алгоритмы, которые гарантированно возвращают приблизительно оптимальное решение при любом вводе.
Рандомизированное округление ( Raghavan & Tompson, 1987 ) - широко используемый подход для разработки и анализа таких алгоритмов аппроксимации . [1] [2] Основная идея состоит в том, чтобы использовать вероятностный метод для преобразования оптимального решения релаксации проблемы в приблизительно оптимальное решение исходной проблемы.
Обзор
Базовый подход состоит из трех этапов:
- Сформулируйте задачу, которую необходимо решить, в виде целочисленной линейной программы (ЦЛП).
- Вычислить оптимальное дробное решение к релаксации линейного программирования (LP) ILP.
- Округлить дробное решение ЛП к целочисленному решению ПДОДИ.
(Хотя этот подход чаще всего применяется к линейным программам, иногда используются и другие виды релаксации. Например, см. Алгоритм аппроксимации Max-Cut, основанный на полуопределенном программировании Гоэманса и Вильямсона .)
Задача на первом этапе - выбрать подходящую целочисленную линейную программу. Требуется знание линейного программирования, в частности, знание того, как моделировать задачи с помощью линейных программ и целочисленных линейных программ. Но для многих задач существует естественная целочисленная линейная программа, которая хорошо работает, например, в приведенном ниже примере Set Cover. (Целочисленная линейная программа должна иметь небольшой пробел в целочисленности ; действительно, рандомизированное округление часто используется для доказательства границ пробелов целочисленности.)
На втором этапе оптимальное дробное решение обычно может быть вычислено за полиномиальное время с использованием любого стандартного алгоритма линейного программирования .
На третьем этапе дробное решение должно быть преобразовано в целочисленное решение (и, следовательно, решение исходной проблемы). Это называется округлением дробного решения. Полученное целочисленное решение должно (доказуемо) стоить не намного больше, чем стоимость дробного решения. Это гарантирует, что стоимость целочисленного решения не намного больше, чем стоимость оптимального целочисленного решения.
Основной метод, используемый для выполнения третьего шага (округления), заключается в использовании рандомизации, а затем использовании вероятностных аргументов для ограничения увеличения стоимости из-за округления (следуя вероятностному методу из комбинаторики). Там вероятностные аргументы используются, чтобы показать существование дискретных структур с желаемыми свойствами. В этом контексте используются такие аргументы, чтобы показать следующее:
- Учитывая любое дробное решение LP, с положительной вероятностью случайный процесс округления дает целочисленное решение это приблизительно по какому-то желаемому критерию.
Наконец, чтобы сделать третий шаг вычислительно эффективным, нужно либо показать, что приблизительно с высокой вероятностью (чтобы шаг мог оставаться рандомизированным) или дерандомизируют шаг округления, обычно используя метод условных вероятностей . Последний метод преобразует процесс рандомизированного округления в эффективный детерминированный процесс, который гарантированно приведет к хорошему результату.
Сравнение с другими приложениями вероятностного метода
Шаг рандомизированного округления отличается от большинства приложений вероятностного метода в двух отношениях:
- Вычислительная сложность шага округления имеет важное значение. Это должно быть реализовано с помощью быстрого (например, полиномиального времени ) алгоритма .
- Распределение вероятностей, лежащее в основе случайного эксперимента, является функцией решения о релаксации экземпляра проблемы. Этот факт имеет решающее значение для доказательства гарантии производительности алгоритма приближения, то есть того, что для любого экземпляра проблемы алгоритм возвращает решение, которое приближает оптимальное решение для этого конкретного экземпляра . Для сравнения, применение вероятностного метода в комбинаторике обычно показывает существование структур, характеристики которых зависят от других параметров входных данных. Например, рассмотрим теорему Турана , которую можно сформулировать как «любой граф с вершины средней степени должен иметь независимый набор размера не менее. (См. Здесь для вероятностного доказательства теоремы Турана .) Хотя существуют графы, для которых эта граница является точной, существуют также графы, у которых независимые множества намного больше, чем. Таким образом, размер независимого множества, которое, согласно теореме Турана, существует в графе, может, в общем, быть намного меньше, чем максимальное независимое множество для этого графа.
Установить пример обложки
В следующем примере показано, как можно использовать рандомизированное округление для разработки алгоритма аппроксимации для задачи Set Cover .
Исправить любой экземпляр Установить обложку над вселенной .
Для шага 1 пусть IP будет стандартной целочисленной линейной программой для установки покрытия для этого экземпляра.
Для шага 2 пусть LP будет релаксацией линейного программирования IP, и вычислим оптимальное решениев LP с помощью любого стандартного алгоритма линейного программирования . (Для этого требуется время, полиномиальное от входного размера.)
(Возможные решения LP - это векторы которые назначают каждый набор неотрицательный вес , так что для каждого элемента , охватывает - общий вес наборов, содержащих не меньше 1, то есть
Оптимальное решение является допустимым решением, стоимость которого
как можно меньше.)
Обратите внимание, что любая обложка набора для дает возможное решение (где для , иначе). Стоимость этого равняется стоимости , это,
Другими словами, линейная программа LP является релаксацией данной задачи о множественном покрытии.
С имеет минимальную стоимость среди возможных решений ЛП, стоимость- нижняя граница стоимости оптимального покрытия множества .
Шаг 3. Шаг рандомизированного округления
Вот описание третьего шага - шага округления, который должен преобразовать минимальную стоимость дробного покрытия набора в допустимое целочисленное решение (соответствует истинной обложке набора).
Шаг округления должен давать что с положительной вероятностью имеет стоимость в пределах небольшого коэффициента стоимости . Тогда (поскольку стоимость - нижняя граница стоимости оптимального покрытия множества), стоимость будет в пределах небольшого коэффициента оптимальной стоимости.
В качестве отправной точки рассмотрим наиболее естественную схему округления:
- Для каждого набора в свою очередь, возьмите с вероятностью , иначе возьмем .
При такой схеме округления ожидаемая стоимость выбранных наборов не превышает , стоимость дробного покрытия. Это хорошо. К сожалению, покрытие не очень хорошее. Когда переменные малы, вероятность того, что элемент не покрывается это о
Таким образом, только постоянная часть элементов будет покрыта ожиданием.
Делать покрывают каждый элемент с высокой вероятностью, стандартная схема округления сначала увеличивает вероятности округления на соответствующий коэффициент. Вот стандартная схема округления:
- Исправить параметр . Для каждого набора в очереди,
- брать с вероятностью , иначе возьмем .
Увеличение вероятностей на увеличивает ожидаемую стоимость на , но делает возможным охват всех элементов. Идея состоит в том, чтобы выбратькак можно меньше, чтобы все элементы доказуемо покрывались с ненулевой вероятностью. Вот подробный анализ.
Лемма (гарантия аппроксимации схемы округления)
- Исправить . С положительной вероятностью схема округления возвращает заданное покрытие стоимости не более (и, следовательно, стоимость раз превышает стоимость оптимального комплекта крышки).
(Примечание: осторожно можно свести к .)
Доказательство
Выход схемы случайного округления имеет желаемые свойства до тех пор, пока не произойдет ни одно из следующих «плохих» событий:
- цена из превышает , или же
- для какого-то элемента , не покрывает .
Ожидание каждого самое большее . По линейности ожидания ожидание самое большее . Таким образом, согласно неравенству Маркова вероятность первого плохого события выше не превосходит.
Для остальных плохих событий (по одному на каждый элемент ) заметим, что, поскольку для любого данного элемента вероятность того, что не покрывается
(Здесь используется неравенство , что строго для .)
Таким образом, для каждого из элементов, вероятность того, что элемент не покрыт, меньше, чем .
Согласно оценке наивного объединения , вероятность того, что один из плохих событий случается меньше чем . Таким образом, с положительной вероятностью плохих событий не бывает и это набор покрытия стоимости не более . QED
Дерандомизация методом условных вероятностей
Приведенная выше лемма показывает существование заданного покрытия стоимости). В этом контексте наша цель - эффективный алгоритм аппроксимации, а не просто доказательство существования, поэтому мы еще не закончили.
Один из подходов - увеличить немного, затем покажите, что вероятность успеха, скажем, равна 1/4. С этой модификацией повторения шага случайного округления несколько раз достаточно, чтобы обеспечить успешный результат с высокой вероятностью.
Такой подход ослабляет коэффициент аппроксимации. Затем мы опишем другой подход, который приводит к детерминированному алгоритму, который гарантированно соответствует коэффициенту аппроксимации приведенного выше доказательства существования. Подход называется методом условных вероятностей .
Детерминированный алгоритм имитирует схему рандомизированного округления: он рассматривает каждый набор в свою очередь, и выбирает . Но вместо того, чтобы делать каждый выбор случайным образом на основе, он делает выбор детерминированно , чтобы удерживать условную вероятность отказа, учитывая выбранные до сих пор варианты, ниже 1 .
Ограничение условной вероятности отказа
Мы хотим иметь возможность устанавливать каждую переменную в свою очередь, чтобы поддерживать условную вероятность отказа ниже 1. Для этого нам нужна хорошая оценка условной вероятности отказа. Оценка будет получена путем уточнения исходного доказательства существования. Это доказательство неявно ограничивает вероятность неудачи математическим ожиданием случайной величины.
- ,
где
- это набор элементов, оставшихся непокрытыми в конце.
Случайная величина может показаться немного загадочным, но оно систематическим образом отражает вероятностное доказательство. Первый член ввозникает из-за применения неравенства Маркова для оценки вероятности первого плохого события (цена слишком высока). Он вносит как минимум 1 вклад в если стоимость слишком высоко. Второй член подсчитывает количество плохих событий второго рода (непокрытых элементов). Он вносит как минимум 1 вклад в если оставляет любой элемент непокрытым. Таким образом, при любом исходе, где меньше 1, должен покрывать все элементы и иметь стоимость, соответствующую требуемой оценке из леммы. Короче говоря, если шаг округления не удается, то. Отсюда следует (по неравенству Маркова ), что- верхняя граница вероятности отказа. Обратите внимание, что приведенное выше рассуждение подразумевается уже в доказательстве леммы, которое также показывает расчетом, что.
Чтобы применить метод условных вероятностей, нам нужно расширить аргумент, чтобы ограничить условную вероятность отказа по мере выполнения шага округления. Обычно это можно делать систематически, хотя это может быть технически утомительно.
Итак, как насчет условной вероятности отказа при итерации на этапе округления наборов? Св любом исходе , где шаг округления терпит неудачу, по неравенству Маркова , то условная вероятность неудачи самого большее условного ожидания.
Затем мы вычисляем условное ожидание , так же как мы рассчитали безусловное ожидание в исходном доказательстве. Рассмотрим состояние процесса округления в конце некоторой итерации. Позволять обозначим рассмотренные до сих пор множества (первые устанавливается в ). Позволять обозначают (частично заданный) вектор (так определяется только если ). Для каждого набора, позволять обозначают вероятность, с которой будет установлено на 1. Пусть содержат еще не покрытые элементы. Тогда условное ожиданиес учетом сделанного выбора, т. е. с учетом , является
Обратите внимание, что определяется только после итерации .
Сохранение условной вероятности отказа ниже 1
Чтобы условная вероятность отказа ниже 1, достаточно сохранить условное ожидание ниже 1. Для этого достаточно сохранить условное ожидание от увеличения. Это то, что будет делать алгоритм. Он установит на каждой итерации, чтобы гарантировать, что
(где ).
в й итерации, как алгоритм может установить чтобы гарантировать, что ? Оказывается, можно просто установитьчтобы минимизировать результирующее значение.
Чтобы понять, почему, сосредоточьтесь на моменте времени, когда итерация начинается. В то время, определяется, но еще не определено --- может принимать два возможных значения в зависимости от того, как устанавливается в итерации . Позволять обозначают значение . Позволять а также , обозначим два возможных значения , в зависимости от того, установлен на 0 или 1 соответственно. По определению условного ожидания
Поскольку средневзвешенное значение двух величин всегда является минимумом из этих двух величин, отсюда следует, что
Таким образом, полагая чтобы минимизировать результирующее значение будет гарантировать, что . Это то, что будет делать алгоритм.
В деталях, что это значит? Рассматривается как функция (со всеми остальными фиксированными количествами) является линейной функцией , а коэффициент в этой функции
Таким образом, алгоритм должен установить в 0, если это выражение положительное, и в 1 в противном случае. Это дает следующий алгоритм.
Алгоритм рандомизированного округления для набора покрытий
ввод: установить систему, вселенная , вектор стоимости
выход: установить обложку (решение стандартной целочисленной линейной программы для набора обложек)
- Вычислить минимальную стоимость частичного покрытия набора (оптимальное решение релаксации ЛП).
- Позволять . Позволять для каждого .
- Для каждого делать:
- Позволять . ( содержит еще не определенные наборы.)
- Если
- затем установите ,
- еще набор а также .
- ( содержит еще не покрытые элементы.)
- Возвращаться .
лемма (гарантия аппроксимации алгоритма)
- Приведенный выше алгоритм возвращает заданное покрытие. стоимости не более умноженная на минимальную стоимость любого (дробного) комплекта обложки.
доказательство
Алгоритм гарантирует, что условное ожидание , , не увеличивается на каждой итерации. Поскольку это условное ожидание изначально меньше 1 (как показано ранее), алгоритм гарантирует, что условное ожидание останется ниже 1. Поскольку условная вероятность отказа не превышает условного ожидания, таким образом алгоритм гарантирует, что условная вероятность отказа остается ниже 1. Таким образом, в конце, когда все варианты определены, алгоритм достигает успешного результата. То есть приведенный выше алгоритм возвращает заданное покрытие. стоимости не более умноженная на минимальную стоимость любого (дробного) комплекта обложки.
Замечания
В приведенном выше примере алгоритм руководствовался условным ожиданием случайной величины. . В некоторых случаях вместо точного условного ожидания вместо этого используется верхняя граница (или иногда нижняя граница) некоторого условного ожидания. Это называется пессимистической оценкой .
Смотрите также
Рекомендации
- ^ Мотвани, Раджив ; Рагхаван, Прабхакар (1995-08-25). Рандомизированные алгоритмы . Издательство Кембриджского университета . ISBN 978-0-521-47465-8.
- ^ Вазирани, Виджай (2002-12-05). Алгоритмы аппроксимации . Springer Verlag . ISBN 978-3-540-65367-7.
- Рагхаван, Прабхакар ; Томпсон, Кларк Д. (1987), "Рандомизированное округление: метод доказуемо хороших алгоритмов и алгоритмических доказательств" , Combinatorica , 7 (4): 365–374, doi : 10.1007 / BF02579324 , S2CID 5749936.
- Raghavan, Prabhakar (1988), "Вероятностное построение детерминированных алгоритмов: аппроксимирующая упаковка целочисленных программ", журнал компьютерных и системных наук , 37 (2): 130-143, DOI : 10,1016 / 0022-0000 (88) 90003-7.
дальнейшее чтение
- Althöfer, Инго (1994), "О разреженных аппроксимаций рандомизированных стратегий и выпуклых комбинаций", Линейная алгебра и ее применения , 199 : 339-355, DOI : 10,1016 / 0024-3795 (94) 90357-3 , MR 1274423
- Хофмайстер, Томас; Lefmann, Ханно (1996), "Вычисление разреженные аппроксимации детерминировано", Линейная алгебра и ее применения , 240 : 9-19, DOI : 10,1016 / 0024-3795 (94) 00175-8 , МР 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