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

Пусть - граф с весовой функцией . Задача max-cut состоит в том, чтобы найти: если весовая функция неотрицательна (т. е. для всех ), тогда для max-cut существует много чрезвычайно простых 2-приближений. Например, мы можем: $G = (V, E, w)$ $w:E\rightarrow \mathbb{R}$

arg max S \subset V \sum (u, v) \in E : u \in S, v \notin S w (u, v)

$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$

w(e)≥0 $w(e) \geq 0$

e∈E $e \in E$

Выберите случайное подмножество вершин $S$ .
Выберите порядок на вершинах и жадно поместите каждую вершину $v$ в $S$ или $\bar{S}$ чтобы максимизировать срезанные края
Внесите локальные улучшения: если в есть какая-либо вершина, $S$ которую можно переместить в $\bar{S}$ для увеличения среза (или наоборот), сделайте этот шаг.

Стандартный анализ всех этих алгоритмов на самом деле показывает, что результирующий срез по крайней мере равен $\frac{1}{2}\sum_{e \in E}w(e)$ , что является верхней границей $1/2$ вес максимального разреза, если $w$ неотрицателен, но если некоторым ребрам разрешено иметь отрицательный вес, это не так!

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

Мой вопрос:

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

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

ds.algorithms graph-theory approximation-algorithms max-cut Аарон Рот
источник

Является ли условие "простой комбинаторный" необходимым здесь?

Сянь-Чи Чанг 之之

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

P≠NP $P \ne NP$

Аарон Рот

Ответы:

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

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

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

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

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

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

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

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

Пусть . Выберите так что (мы оправдать это позже). Разрез с весом в имеющий и на противоположных сторонах, теперь становится разрезом с весом . Это означает, что оптимальный срез в имеет вес . Наш новый алгоритм находит разрез в с весом не менее . Это переводит в разрез в исходном графе с весом не менее (поскольку все разрезы в с положительным весом отделяются $f=(a - (n-2)d)$ $a$ $f \approx - 0.98 OPT$ $c$ $G$ $u$ $v$ $c - 0.98 OPT$ $G^*$ $0.02 OPT$ $G^*$ $0.01 OPT$ $G$ $0.99OPT$ $G^*$ $u$ и ), что лучше, чем результат неприемлемости. $v$

Нет проблем с выбором достаточно большого, чтобы сделать любой разрез с и на одной стороне отрицательным, поскольку мы можем выбрать настолько большим, насколько мы хотим. Но как же мы выбираем так , что , когда мы не знали ? Мы можем аппроксимировать очень хорошо ... если мы позволим быть сумма весов ребер в , мы знаем . Таким образом, у нас есть довольно узкий диапазон значений для , и мы можем перебирать принимая все значения от до $d$ $u$ $v$ $d$ $a$ $f \approx -.99OPT$ $OPT$ $OPT$ $T$ $G$ $\frac{1}{2}T \leq OPT \leq T$ $f$ $f$ $-.49T$ $-.99T$ с интервалами . Для одного из этих интервалов мы гарантируем, что , и поэтому одна из этих итераций гарантированно вернет хороший результат. $0.005T$ $f \approx -0.98 OPT$

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

Питер Шор
источник

Но каков ваш и ? Обычная постановка задачи макс-среза не имеет «специальные узлы» , которые должны быть отделены.

u $u$

v $v$

Юкка Суомела

Привет Йен - я не думаю, что это работает, хотя Почему обязательно должны существовать любые и , которые разделены макс-разрезом в исходном графике и остаются разделенными макс-разрезом после того, как между ними добавлено сильное отрицательное ребро? Рассмотрим, например, полный граф - добавление одного произвольно отрицательного ребра в любом месте не меняет значение среза вообще.

u $u$

v $v$

Аарон Рот

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

|S|⋅|S¯|⋅a $|S|\cdot|\bar{S}|\cdot a$

S $S$

Аарон Рот

@Peter: В пункте после того, я цитировал вы выбираете достаточно малы , чтобы . Вы не можете смело выбирать быть достаточно большим в одном пункте , и достаточно мало в следующем! В частности, нет возможности выбрать и чтобы гарантировать, что для всех и одновременно имеют . Это следует из того, что для всех означает, что .

a $a$

f≈−0.98OPT $f \approx -0.98 OPT$

a $a$

d $d$

c+a−(n−2)d>c−dm $c+a-(n-2)d>c-dm$

0≤m≤n $0\le m \le n$

a−(n−2)d=f≈−0.98⋅OPT $a-(n-2)d = f\approx -0.98 \cdot OPT$

c+a−(n−2)d>c−dm $c+a-(n-2)d>c-dm$

0≤m≤n $0\le m \le n$

f=a−(n−2)d>0 $f=a-(n-2)d > 0$

Уоррен Шуди

@Warren, вы выбираете достаточно большим, чтобы для всех разрезов. Это можно сделать, выбрав достаточно большим. Вы затем выбрать нужном размере , так что оптимальный разрез чуть - чуть выше . Прочитайте два последних абзаца моего ответа.

d $d$

c−dm<0 $c-dm<0$

d $d$

a $a$

0 $0$

Питер Шор

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

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

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

Сянь-Чжи Чан 張顯之
источник

проблема в Alon-Naor аналогична, но я не думаю, что есть сокращение, сохраняющее соотношение. их задача - максимизировать

где

- матрица

. для max-cut и его близких родственников крайне важно, чтобы

xTMy $x^TMy$

x,y∈{±1}n $x, y \in \{\pm 1\}^n$

M $M$

n×n $n \times n$

x=y $x = y$

Сашо Николов

@SashoNikolov: для обрезанной нормы это несущественно, вплоть до постоянных факторов, независимо от того, требуем мы

или нет. x=y $x=y$

Дэвид

@ Давид Я знаю это сокращение, но утверждение, которое на самом деле верно, таково, что

где все максимумы превышают

, а

симметрично с неотрицательной диагональю. Однако проблема

maxx|xTMx|≤maxx,yxTMy≤4maxx|xTMx| $\max_x |x^TMx| \leq \max_{x, y}{x^TMy} \leq 4 \max_x |x^TMx|$

{−1,1}n $\{-1, 1\}^n$

M $M$

maxx|xTMx| $\max_x |x^TMx|$ может иметь значение, отличное от

(что нам нужно для MaxCut). Например, рассмотрим

, где

- матрица всех единиц

. Вы можете видеть, что

составляет около

, в то время как

это

. maxxxTMx $\max_x x^TMx$

M=I−J $M = I-J$

J $J$

n×n $n\times n$

maxxxTMx $\max_{x}{x^TMx}$

n/2 $n/2$

maxx|xTMx| $\max_{x}{|x^TMx|}$

n2−n $n^2 - n$

Сашо Николов

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

Задача MaxQP - это задача аппроксимации квадратичной формы для матрицы , где лежит в пределах . MaxCut можно записать в этой форме, установив $x^TMx$ $n \times n$ $M$ $x$ $\{\pm 1\}^n$ где- единичная матрица, а- матрица смежности. Алгоритм MaxQP Чарикара и Wirthдаетприближение для MaxQPтех поркакимеют неотрицательную диагональ. Так что, пока, MaxCut с отрицательными весами имеет логарифмический. $M = \frac{1}{2n}(\sum{w_e})I - \frac{1}{2}A$ $I$ $A$ $O(\log n)$ $M$ $\sum{w_e} \geq 0$

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