Рандомизированное округление решений для линейных программ

Question

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

• Примально двойная схема
• Рандомизированное округление

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

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

Как показывают рандомизированные схемы округления, что ограничения не нарушаются?

Казалось бы, что наивно переворачивая монету, в то время как решение 0-1 может нарушить ограничения! Любая помощь, освещающая эту проблему, будет оценена. Спасибо.

Answer 1

Конечно, если вы вокруг, вы должны проверить, что округление сохраняет выполнимость.

Давайте, например, рассмотрим расслаблен Сформулирование LP Vertex-Cover. $$ begin {array} {lll} text {min} & sum_ {v in v} c (v) x_v & text {st} & x_u+x_v ge1, & Quad (u, v ) in e & x_v ge 0. & Quad V in v end {array} $$

Известно, что решение этой проблемы состоит в получке, то есть каждая переменная составляет либо 0 $, $ 1 $, либо $ 1/2 $. Схема округления работает следующим образом, всякий раз, когда ваше решение содержит $ x_v = 1/2 $ you округлять и установить $ x_v = 1 $. Ограничениями ILP были $$ begin {array} {lll} & x_u+x_v ge1, & Quad (u, v) in e & x_v in {0,1 }. & Quad V in v end {массив} $$ Оба ограничения выполняются после округления. И у вас есть хорошая 2-аппексимация.

Answer 2

Да, это сбивает с толку на первом виде.

Я вижу это так:

Шаг 1) Сгенерировать линейное программное решение [все ограничения линейной программы выполняются здесь - за исключением того, что это не является целым решением],

Шаг 2) Рандомизируйте его (измените значение на целые числа в соответствии с выбранным вами распределением вероятностей),

Шаг 3) Убедитесь, что рандомизированное решение является правильным (внесение мало изменений на нем).

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

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

Смотрите это для ссылки: 1