Corte máximo com arestas com peso negativo

$G = (V, E, w)$$w:E\rightarrow \mathbb{R}$

1. Escolher um subconjunto aleatório de vértices .$S$
2. Escolha uma ordem nos vértices e coloque avidamente cada vértice em ou para maximizar as arestas cortadas até o momento$v$$S$$\bar{S}$
3. Faça melhorias locais: se houver algum vértice em que possa ser movido para para aumentar o corte (ou vice-versa), faça a mudança.$S$$\bar{S}$

A análise padrão de todos esses algoritmos realmente mostra que o corte resultante é pelo menos tão grande quanto , que é um limite superior em o peso do corte máximo se não for negativo - mas se algumas arestas tiverem peso negativo, não será!$\frac{1}{2}\sum_{e \in E}w(e)$$1/2$$w$

Por exemplo, o algoritmo 1 (escolha um subconjunto aleatório de vértices) pode falhar claramente em gráficos com pesos de borda negativos.

Minha pergunta é:

Existe um algoritmo combinatório simples que obtém uma aproximação O (1) para o problema de corte máximo em gráficos que podem ter pesos de borda negativos?

Para evitar o possível problema do valor máximo de corte , permitirei que e / ou fique satisfeito com algoritmos que resultam em pequeno erro aditivo, além de uma aproximação de fator multiplicativo.0 ∑ e ∈ E w ( e ) > $0$$\sum_{e \in E}w(e) > 0$

Aqui foi minha primeira tentativa de discussão. Estava errado, mas eu o corrigi após o "EDIT:"

Se você pudesse resolver de maneira eficiente o problema de corte máximo com pesos negativos nas bordas, não poderia usá-lo para resolver o problema de corte máximo com pesos positivos nas bordas? Comece com um problema de corte máximo que você deseja resolver cuja solução ideal é b . Agora, coloque uma grande margem de peso negativo (com peso - a ) entre u e v . A solução ideal do novo problema é b - a , portanto, nosso hipotético algoritmo de aproximação fornecerá uma solução com corte máximo cujo valor é no máximo ( b - a ) / 2 pior que o ideal. No gráfico original, o corte máximo ainda é no máximo$b$$-a$$u$$v$$b-a$$(b-a)/2$( b - a ) / 2 pior que o ideal. Se você escolher um perto de b , isso viola o resultado inapproximability que, se P ≠ NP, você não pode aproximada max-corte para melhor do que um 16 / 17 de fator. $(b-a)/2$$a$$b$$\neq$$16/17$

EDITAR:

O algoritmo acima não funciona porque você não pode garantir que u e v estejam em lados opostos do corte no novo gráfico, mesmo se eles estivessem originalmente. Eu posso corrigir isso da seguinte maneira, no entanto.$u$$v$

Vamos supor que temos um algoritmo de aproximação que nos dará um corte dentro de um fator de 2 de OPT, desde que a soma de todos os pesos das arestas seja positiva.

Como acima, comece com um gráfico G com todos os pesos não negativos nas arestas. Encontraremos um gráfico modificado G ∗ com alguns pesos negativos, de modo que, se pudermos aproximar o corte máximo de G ∗ dentro de um fator de 2, podemos aproximar muito bem o corte máximo de G ..$G$$G^*$$G^*$$G$

Escolha dois vértices u e v , e espero que eles estão em lados opostos do corte máx. (Você pode repetir isso para todo o possível v para garantir que uma tentativa funcione.) Agora, coloque um grande peso negativo - d em todas as arestas ( u , x ) e ( v , x ) para x ≠ u , ve um grande peso positivo a na borda ( u , v ) . Assume-se que a óptima corte tem peso S P T .$u$$v$$v$$-d$$(u,x)$$(v,x)$$x \neq u,v$$a$$(u,v)$$OPT$

Um corte com valor c em G , onde os vértices u e v estão do mesmo lado do corte, agora tem valor em c - 2 d m, em que m é o número de vértices do outro lado do corte. Um corte com ( u , v ) em lados opostos com o valor original c agora tem o valor c + a - ( n - 2 ) d . Assim, se escolhermos d grande o suficiente, poderemos forçar todos os cortes com u e $c$$G$$u$$v$$c - 2dm$$m$$(u,v)$$c$$c + a - (n-2)d$$d$$u$$v$no mesmo lado para ter valor negativo, por isso, se existe qualquer corte com valor positivo, em seguida, o corte óptima em L * terá u e v em lados opostos. Observe que estamos adicionando um peso fixo ( a - ( n - 2 ) d ) a qualquer corte com u e v em lados opostos.$G^*$$u$$v$$(a - (n-2)d)$$u$$v$

Seja f = ( a - ( n - 2 ) d ) . Escolha a para que f ≈ - 0,98 O P T (justificaremos isso mais tarde). Um corte com peso c em L possuindo u e v em lados opostos torna-se agora um corte com peso c - 0,98 S P T . Isso significa que o corte ideal em G ∗ tem peso 0,02 O P $f=(a - (n-2)d)$$a$$f \approx - 0.98 OPT$$c$$G$$u$$v$$c - 0.98 OPT$$G^*$$0.02 OPT$. O nosso novo algoritmo encontra um corte em L * com o peso, pelo menos, 0,01 S P T . Isso se traduz em um corte no gráfico original G com peso de pelo menos 0,99 O P T (uma vez que todos os cortes em G ∗ com peso positivo separam u e v ), o que é melhor que o resultado da inadequação.$G^*$$0.01 OPT$$G$$0.99OPT$$G^*$$u$$v$

Não há problema em escolher d grande o suficiente para fazer qualquer corte com u e v do mesmo lado negativo, pois podemos escolher d tão grande quanto queremos. Mas como escolhemos um modo que f ≈ - 0,99 O P T quando não conhecíamos O P T ? Podemos aproximar muito bem O P T ... se deixarmos T ser a soma dos pesos das arestas em G , sabemos $d$$u$$v$$d$$a$$f \approx -.99OPT$$OPT$$OPT$$T$$G$2 T≤SPT≤T. Portanto, temos uma gama bastante estreita de valores def, e podemos iterarftomar todos os valores entre-0,49Te-0,99Tem intervalos de0,005T. Para um desses intervalos, garantimos quef≈-0,98OPTe, portanto, uma dessas iterações deve retornar um bom corte.$\frac{1}{2}T \leq OPT \leq T$$f$$f$$-.49T$$-.99T$$0.005T$$f \approx -0.98 OPT$

Finalmente, precisamos verificar se o novo gráfico possui pesos de borda cuja soma é positiva. Começamos com um gráfico cujos pesos das arestas tinham soma T e adicionamos f à soma dos pesos das arestas. Desde - 0,99 T ≤ f ≤ - 0,49 T , estamos bem $T$$f$$-.99T \leq f \leq -.49T$

No artigo " Approximate Max Cut " de S. Har-Peled, a última linha do artigo mencionou que a versão ponderada real do max-cut foi discutida em

Aproximando a norma de corte através da desigualdade de grothendieck , Noga Alon e Assaf Naor, SIAM Journal on Computing, 2006.

Na verdade, é um algoritmo SDP, e parece-me que a taxa de aproximação é de 0,56, embora não tenha certeza se a redução discutida no artigo está preservando a taxa. Talvez uma análise mais profunda do artigo ajude!

Your problem has a logarithmic approximation by reduction to a quadratic programming problem.

The MaxQP problem is the problem of approximating the quadratic form $x^TMx$ for a $n \times n$ matrix $M$, where $x$ ranges over $\{\pm 1\}^n$. MaxCut can be written in this form by setting $M = \frac{1}{2n}(\sum{w_e})I - \frac{1}{2}A$ where $I$ is the identity matrix and $A$ is the adjacency matrix. The MaxQP algorithm of Charikar and Wirth gives an $O(\log n)$ approximation for MaxQP as long as $M$ has a non-negative diagonal. So as long as $\sum{w_e} \geq 0$, MaxCut with negative weights has a logarithmic approximation.