Интегральный разрыв и коэффициент аппроксимации

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

Некоторые алгоритмы могут иметь лучший коэффициент аппроксимации, чем разрыв интегральности для некоторой задачи, но я не знаю, существует ли такой пример или нет. Если ответ «да», не могли бы вы привести несколько примеров?

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

Этот вопрос связан с [вопросом: важность разрыва целостности] .

ds.algorithms approximation-algorithms linear-programming integrality-gap Snowie
источник

Я предположил бы, что геометрический TSP был бы примером такой проблемы, но у меня нет никаких ссылок.

Юкка Суомела

А как насчет проблем, которые допускают PTAS с использованием стратегии переключения? Есть ли у кого-то из них формулировка ИС с сколь угодно малым разрывом интегральности?

Юкка Суомела

@Jukka геометрический TSP является хорошим примером. Пример разрыва 4/3 целочисленности является кратчайшим путем метрики на плоский графике, и это должно быть возможным , чтобы превратить в экземпляр евклидов TSP или

TSP в плоскости с

зазором

ℓ_{1}

$\ell_1$

1 + ϵ

$1+\epsilon$

Лука Тревисан

Я слышал, что в качестве интересного открытого вопроса упоминается, можно ли реализовать PTAS для задач на плоских графах, используя постоянное число уровней релаксаций Шерали-Адамса или Лассерра. (Там, где постоянная зависит от соотношения аппроксимации, которого нужно достичь.) Должно быть известно или, по крайней мере, доказано современными методами, что у задач с графами, в которых имеются PTAS в плотных графах (например, максимальное сечение), также есть семейство полиномов. размерные релаксации с сколь угодно малыми зазорами интегральности.

Лука Тревизан

Смежный вопрос: есть ли проблема, которая доказана, что любой LP многочленного размера не может дать текущий наилучший известный коэффициент приближения? Можно ли доказать такую вещь, даже для некоторых ограниченных типов пластинок?

Дану

Ответы:

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

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

Интригующим является расположение объекта с емкостью. Здесь естественная релаксация имеет неограниченную щель интегральности. Тем не менее, алгоритмы на основе локального поиска дают приближения с постоянными множителями.

Еще одна очень интересная (хотя это проблема максимизации) статья: http://www.cis.upenn.edu/~sanjeev/postscript/FOCS09_MaxMin.pdf . Здесь у LP большой пробел, и все же алгоритм, который использует этот LP, может работать лучше.

Кунал
источник

Большое спасибо. Этот ответ содержит то, что я искал, особенно документ FOCS, написанный Chakrabarty et al. (эта статья меня так интересует) Поэтому я установил этот ответ как принятый. Я все еще ищу больше примеров, и поэтому любой, кто может привести другие примеры, будет высоко оценен.

Снежок

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

Например, стандартная релаксация линейного программирования max cut имеет разрыв интегральности 1/2, и это справедливо даже для гораздо более сложных релаксаций линейного программирования (см. Де ла Вега-Кеньон и Шенебек-Тревизан-Тулсиани), но Гоманс Алгоритм Уильямсона-SDP имеет приближение .878 ...

$\Omega(\log n)$ $O(\sqrt{\log n})$

Возможно, менее известный, Карлофф и Цвик показывают, что используя SDP можно приблизить Max 3SAT в версии, в которой пункты могут иметь 1, 2 или 3 литерала, в течение 7/8, в то время как Геманс и Уильямсон изучали ослабление линейного программирования, которое они используется для доказательства приближения 3/4 (Яннакакис дал приближение 3/4 ранее другими методами), и релаксация Гоемана-Уильямсона LP Max 3SAT, как легко видеть, имеет разрыв целостности 3/4.

Лука Тревизан
источник

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

YI WU
источник