Макс-срез с отрицательными краями веса

35

Пусть - граф с весовой функцией . Задача max-cut состоит в том, чтобы найти: если весовая функция неотрицательна (т. е. w (e) \ geq 0 для всех e \ in E ), тогда для max-cut существует много чрезвычайно простых 2-приближений. Например, мы можем:G=(V,E,w)w:ERArgmaxSV(u,v)E:uS,vSw(u,v)

argmaxSV(u,v)E:uS,vSw(u,v)
w(e)0w(e)0eEeE
  1. Выберите случайное подмножество вершин SS .
  2. Выберите порядок на вершинах и жадно поместите каждую вершину vv в SS или ˉSS¯ чтобы максимизировать срезанные края
  3. Внесите локальные улучшения: если в S есть какая-либо вершина, SSкоторую можно переместить в ˉSS¯ для увеличения среза (или наоборот), сделайте этот шаг.

Стандартный анализ всех этих алгоритмов на самом деле показывает, что результирующий срез по крайней мере равен 12eEw(e)12eEw(e) , что является верхней границей 1/21/2 вес максимального разреза, если ww неотрицателен, но если некоторым ребрам разрешено иметь отрицательный вес, это не так!

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

Мой вопрос:

Существует ли простой комбинаторный алгоритм, который получает приближение O (1) к задаче максимального разреза на графах, которые могут иметь отрицательные веса ребер?

Чтобы избежать, возможно, липкой проблемы, связанной с принятием значения max-cut 00 , я позволю, чтобы Σ е E ш ( е ) > 0eEw(e)>0 , и / или был бы удовлетворен алгоритмами, которые приводят к небольшой аддитивной ошибке в дополнение к мультипликативный коэффициент приближения.

Аарон Рот
источник
1
Является ли условие "простой комбинаторный" необходимым здесь?
Сянь-Чи Чанг 之 之
Меня больше всего интересует простой комбинаторный алгоритм, такой как 2-приближения для случая положительного веса. Обратите внимание, что я спрашиваю о любом O (1) приближении, поэтому я ожидаю, что если какой-либо алгоритм может достичь этого, это должно быть возможно с помощью простого. Но мне также было бы интересно узнать, каковы гарантии производительности для алгоритмов SDP на графах с отрицательным весом ребер или как доказательство отсутствия алгоритма аппроксимации с постоянным множителем, если . P N PPNP
Аарон Рот

Ответы:

28

Здесь была моя первая попытка спора. Это было неправильно, но я исправил это после "РЕДАКТИРОВАТЬ:"

Если бы вы могли приблизительно решить проблему максимального среза с отрицательными весами, не могли бы вы использовать это для решения проблемы максимального среза с положительными весами? Начните с задачи максимального разреза, которую вы хотите решить, чье оптимальное решение - . Теперь поместите большую отрицательную границу веса (с весом ) между и . Оптимальным решением новой задачи является , поэтому наш алгоритм гипотетической аппроксимации даст вам решение с максимальным разрезом, значение которого не более хуже оптимального. На исходном графике максимальный срез по-прежнему не более хуже оптимального. Если вы выбираете близком кб - у V б - ( б - ) / 2 ( б - ) / 2 б 16 / 17bauvba(ba)/2(ba)/2ab, это нарушает результат неприемлемости того, что если P NP, вы не можете приблизить максимальное сокращение к значению, превышающему . 16/17

РЕДАКТИРОВАТЬ:

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

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

Как и выше, начните с графа со всеми неотрицательными весами на ребрах. Мы найдем модифицированный граф с некоторыми отрицательными весами, так что, если мы сможем приблизить максимальный разрез с коэффициентом 2, мы сможем очень хорошо аппроксимировать максимальный разрезG G G GGGGG

Выберите две вершины и и надейтесь, что они находятся на противоположных сторонах максимального среза. (Вы можете повторить это для всех возможных чтобы убедиться, что одна попытка работает.) Теперь поместите большой отрицательный вес на все ребра и для и a большой положительный вес на ребре . Предположим, что оптимальный срез имеет вес .u v v - d ( u , x ) ( v , x ) x u , v a ( u , v ) O P Tuvvd(u,x)(v,x)xu,va(u,v)O PT

Вырез со значением в , где вершины и находятся на одной и той же стороне разреза, теперь имеет значение в где - количество вершин на другой стороне разреза. Разрез с на противоположных сторонах с исходным значением теперь имеет значение . Таким образом, если мы выберем достаточно большим, мы можем заставить все срезы с и на одной стороне иметь отрицательное значение, поэтому, если есть какой-либо срез с положительным значением, то оптимальный срез в будет иметь иc G u v c - 2 d m m ( u , v ) c c + a - ( n - 2 ) d d u v G u v ( a - ( n - 2 ) d ) u vсгUvс - 2 дмм( U , V )сc + a - ( n - 2 ) ddUvг*Uvна противоположных сторонах. Обратите внимание, что мы добавляем фиксированный вес к любому разрезу с и на противоположных сторонах.(a(n2)d)uv

Пусть . Выберите так что (мы оправдать это позже). Разрез с весом в имеющий и на противоположных сторонах, теперь становится разрезом с весом . Это означает, что оптимальный срез в имеет вес . Наш новый алгоритм находит разрез в с весом не менее . Это переводит в разрез в исходном графе с весом не менее (поскольку все разрезы в с положительным весом отделяютсяе = ( - ( п - 2 ) д ) е - 0,98 О Р Т с G U V с - 0,98 О Р Т О * 0,02 О Р Т О * 0,01 О Р Т О 0,99 О Р Т С * U vf=(a(n2)d)af0.98OPTcGuvc0.98OPTG0.02OPTG0.01OPTG0.99OPTGu и ), что лучше, чем результат неприемлемости.v

Нет проблем с выбором достаточно большого, чтобы сделать любой разрез с и на одной стороне отрицательным, поскольку мы можем выбрать настолько большим, насколько мы хотим. Но как же мы выбираем так , что , когда мы не знали ? Мы можем аппроксимировать очень хорошо ... если мы позволим быть сумма весов ребер в , мы знаем . Таким образом, у нас есть довольно узкий диапазон значений для , и мы можем перебирать принимая все значения от доd u v d a f - .99 O P T O P T O P T T G 1duvdaf.99OPTOPTOPTTG2 TOPTTff-.49T-.99T0.005Tf-0,98OPT12TOPTTff.49T.99Tс интервалами . Для одного из этих интервалов мы гарантируем, что , и поэтому одна из этих итераций гарантированно вернет хороший результат.0.005Tf0.98OPT

Наконец, нам нужно проверить, что новый граф имеет веса ребер, сумма которых положительна. Мы начали с графика, у которого веса ребер имели сумму , и добавили к сумме весов ребер. Так как , мы в порядке T f - .99 T f - .49 TTf.99Tf.49T

Питер Шор
источник
1
Но каков ваш и ? Обычная постановка задачи макс-среза не имеет «специальные узлы» , которые должны быть отделены. у vuv
Юкка Суомела
3
Привет Йен - я не думаю, что это работает, хотя Почему обязательно должны существовать любые и , которые разделены макс-разрезом в исходном графике и остаются разделенными макс-разрезом после того, как между ними добавлено сильное отрицательное ребро? Рассмотрим, например, полный граф - добавление одного произвольно отрицательного ребра в любом месте не меняет значение среза вообще. у vuv
Аарон Рот
2
Одна из проблем заключается в том, что если вы добавляете отрицательное ребро между каждой парой вершин, то вы изменяете значение разных срезов на разные величины. (Вычитаем, скажем, из значения разреза ). Таким образом, у нас есть проблема, заключающаяся в том, что идентичность максимального разреза в модифицированном графе не обязательно соответствует максимальному разрезу в исходном графе. | S | | ˉ S | S|S||S¯|aS
Аарон Рот
1
@Peter: В пункте после того, я цитировал вы выбираете достаточно малы , чтобы . Вы не можете смело выбирать быть достаточно большим в одном пункте , и достаточно мало в следующем! В частности, нет возможности выбрать и чтобы гарантировать, что для всех и одновременно имеют . Это следует из того, что для всех означает, что . a f - 0,98 O P T a a d c + a - ( n - 2 ) d > c - d m 0 m n a - ( n - 2 ) d = f - 0,98 O P T c + a - ( n - 2 ) d > c -af0.98OPTaadc+a(n2)d>cdm0mna(n2)d=f0.98OPTdmc+a(n2)d>cdm0mn0mnf=a(n2)d>0f=a(n2)d>0
Уоррен Шуди
2
@Warren, вы выбираете достаточно большим, чтобы для всех разрезов. Это можно сделать, выбрав достаточно большим. Вы затем выбрать нужном размере , так что оптимальный разрез чуть - чуть выше . Прочитайте два последних абзаца моего ответа. ddcdm<0cdm<0ddaa00
Питер Шор
11

В статье « Приблизительный максимальный срез » С. Хар-Пеледа в последней строке статьи упоминается, что реальный взвешенный вариант максимального среза обсуждался в

Приближение строгой нормы через неравенство Гротендика , Нога Алон и Ассаф Наор, SIAM Journal of Computing, 2006.

Это действительно алгоритм SDP, и мне кажется, что коэффициент аппроксимации равен 0,56, хотя я не уверен, что сокращение, обсуждаемое в статье, является сохранением коэффициента. Может быть, поможет более глубокий взгляд на бумагу!

Сянь-Чжи Чан 張顯 之
источник
проблема в Alon-Naor аналогична, но я не думаю, что есть сокращение, сохраняющее соотношение. их задача - максимизировать x T M y, где x , y { ± 1 } n, а M - матрица n × n . для max-cut и его близких родственников крайне важно, чтобы x = yxTMyx,y{±1}nMn×nx=y
Сашо Николов
@SashoNikolov: для обрезанной нормы это несущественно, вплоть до постоянных факторов, независимо от того, требуем мы x = y или нет. x=y
Дэвид
@ Давид Я знаю это сокращение, но утверждение, которое на самом деле верно, таково, что max x | х т м х | max x , y x T M y4 max x | х т м х | где все максимумы превышают { - 1 , 1 } n , а M симметрично с неотрицательной диагональю. Однако проблема max x | х т м х |maxx|xTMx|maxx,yxTMy4maxx|xTMx|{1,1}nMmaxx|xTMx|может иметь значение, отличное от max x x T M x (что нам нужно для MaxCut). Например, рассмотрим M = I - J , где J - матрица всех единиц n × n . Вы можете видеть, что max x x T M x составляет около n / 2 , в то время как max x | х т м х | это n 2 - n . maxxxTMxM=IJJn×nmaxxxTMxn/2maxx|xTMx|n2n
Сашо Николов
6

Ваша задача имеет логарифмическое приближение путем сведения к задаче квадратичного программирования.

Задача MaxQP - это задача аппроксимации квадратичной формы x T M x для матрицы n × n M , где x лежит в пределах { ± 1 } n . MaxCut можно записать в этой форме, установив M = 1xTMx2 п (Σже)я-12 A,гдеI- единичная матрица, аA- матрица смежности. Алгоритм MaxQP Чарикара и WirthдаетO(журналN)приближение для MaxQPтех поркакМимеют неотрицательную диагональ. Так что, покаЕже0, MaxCut с отрицательными весами имеет логарифмический.

Сашо Николов
источник