Corte máximo con bordes de peso negativo

35

Sea una gráfica con la función de peso . El problema de max-cut es encontrar: If la función de peso no es negativa (es decir, w (e) \ geq 0 para todas las e \ en E ), entonces hay muchas aproximaciones de 2 extremadamente simples para max-cut. Por ejemplo, podemos: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. Elija un subconjunto aleatorio de vértices SS .
  2. Elija un orden en los vértices y coloque con avidez cada vértice vv en SS o ˉSS¯ para maximizar los bordes cortados hasta el momento
  3. Realice mejoras locales: si hay algún vértice en SS que se pueda mover a ˉSS¯ para aumentar el corte (o viceversa), realice el movimiento.

El análisis estándar de todos estos algoritmos en realidad muestra que el corte resultante es al menos tan grande como 12eEw(e)12eEw(e) , que es un límite superior en 1/21/2 el peso del corte máximo si ww no es negativo, pero si se permite que algunos bordes tengan peso negativo, ¡no lo es!

Por ejemplo, el algoritmo 1 (elija un subconjunto aleatorio de vértices) puede fallar claramente en gráficos con pesos de borde negativos.

Mi pregunta es:

¿Existe un algoritmo combinatorio simple que obtenga una aproximación O (1) al problema de corte máximo en gráficos que pueden tener pesos de borde negativos?

Para evitar el posible problema del valor máximo de toma de corte 00 , permitiré que e E w ( e ) > 0eEw(e)>0 , y / o esté satisfecho con los algoritmos que resultan en un pequeño error aditivo además de una aproximación de factor multiplicativo.

Aaron Roth
fuente
1
¿Es esencial aquí la condición "combinatoria simple"?
Hsien-Chih Chang 張顯 之
Estoy más interesado en un algoritmo simple y combinatorio como las 2 aproximaciones para el caso de peso positivo. Tenga en cuenta que estoy preguntando acerca de cualquier aproximación O (1), por lo que esperaría que si algún algoritmo puede lograr esto, debería ser posible con uno simple. Pero también me interesarían las garantías de rendimiento para los algoritmos SDP en gráficos con pesos de borde negativos, o la evidencia de que no existe un algoritmo de aproximación de factor constante si . P N PPNP
Aaron Roth

Respuestas:

28

Aquí fue mi primer intento de una discusión. Estaba mal, pero lo arreglé después de "EDITAR:"

Si pudiera resolver eficientemente el problema de corte máximo con pesos de borde negativos, ¿no podría usar eso para resolver el problema de corte máximo con pesos de borde positivos? Comience con un problema de corte máximo que desee resolver cuya solución óptima es . Ahora, coloque un borde de peso negativo grande (con peso ) entre y . La solución óptima del nuevo problema es , por lo que nuestro algoritmo de aproximación hipotético le dará una solución con un corte máximo cuyo valor es como máximo peor que el óptimo. En el gráfico original, el corte máximo sigue siendo como máximo peor que el óptimo. Si eliges cerca deb - una u v b - una ( b - a ) / 2 ( b - a ) / 2 un b 16 / 17bauvba(ba)/2(ba)/2ab, esto viola el resultado de inaplicabilidad de que si P NP, no puede aproximar el corte máximo a un factor mejor que . 16/17

EDITAR:

El algoritmo anterior no funciona porque no puede garantizar que y estén en lados opuestos del corte en el nuevo gráfico, incluso si estaban originalmente. Sin embargo, puedo arreglar esto de la siguiente manera.tu vuv

Supongamos que tenemos un algoritmo de aproximación que nos dará un corte dentro de un factor de 2 de OPT siempre que la suma de todos los pesos de los bordes sea positiva.

Como arriba, comience con un gráfico con todos los pesos no negativos en los bordes. Encontraremos un gráfico modificado con algunos pesos negativos, de modo que si podemos aproximar el corte máximo de dentro de un factor de 2, podemos aproximar muy bien el corte máximo deG G G GGGGG

Elija dos vértices y , y espere que estén en lados opuestos del corte máximo. (Puede repetir esto para todos los posibles para asegurarse de que un intento funcione). Ahora, coloque un peso negativo grande en todos los bordes y para , y a gran peso positivo en el borde . Suponga que el corte óptimo tiene peso .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)OPT

Un corte con valor en , donde los vértices y están en el mismo lado del corte, ahora tiene un valor en donde es el número de vértices en el otro lado del corte. Un corte con en lados opuestos con el valor original ahora tiene el valor . Por lo tanto, si elegimos suficientemente grande, podemos forzar que todos los cortes con y en el mismo lado tengan un valor negativo, por lo que si hay algún corte con valor positivo, entonces el corte óptimo en tendrá yc 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 vcGuvc2dmm(u,v)cc+a(n2)dduvGuven lados opuestos. Tenga en cuenta que estamos agregando un peso fijo a cualquier corte con y en lados opuestos.(a(n2)d)uv

Sea . Elija para que (lo justificaremos más adelante). Un corte con peso en con y en lados opuestos ahora se convierte en un corte con peso . Esto significa que el corte óptimo en tiene un peso de . Nuestro nuevo algoritmo encuentra un corte en con un peso de al menos . Esto se traduce en un corte en el gráfico original con un peso de al menos (ya que todos los cortes en con peso positivo se separanf = ( a - ( n - 2 ) d ) a f - 0.98 O P T c G u v c - 0.98 O P T G 0.02 O P T G 0.01 O P T G 0.99 O P T G u vf=(a(n2)d)af0.98OPTcGuvc0.98OPTG0.02OPTG0.01OPTG0.99OPTGu y ), que es mejor que el resultado de inaproximabilidad.v

No hay problema con elegir suficientemente grande como para hacer cualquier corte con y en el mismo lado negativo, ya que podemos elegir tan grande como queramos. Pero, ¿cómo elegimos para que cuando no sabíamos ? Podemos aproximar muy bien ... si dejamos que sea la suma de los pesos de las aristas en , sabemos . Por lo tanto, tenemos un rango de valores bastante estrecho para , y podemos iterar sobre tomando todos los valores entre yd 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.99Ta intervalos de . Para uno de estos intervalos, tenemos la garantía de que , por lo que una de estas iteraciones garantiza un buen corte.0.005Tf0.98OPT

Finalmente, debemos verificar que el nuevo gráfico tenga pesos de borde cuya suma sea positiva. Comenzamos con un gráfico cuyos pesos de borde tenían la suma , y agregamos a la suma de los pesos de borde. Desde , estamos bien T f - .99 T f - .49 TTf.99Tf.49T

Peter Shor
fuente
1
Pero, ¿cuáles son tus y ? La formulación habitual del problema de corte máximo no tiene ningún "nodo especial" que deba separarse. tu vuv
Jukka Suomela
3
Hola, Ian. No creo que eso funcione. ¿Por qué necesariamente tiene que existir un y que estén separados por el corte máximo en el gráfico original y permanezcan separados por el corte máximo después de que se agregue un borde negativo pesado entre ellos? Considere, por ejemplo, el gráfico completo: agregar un solo borde arbitrariamente negativo en cualquier lugar no cambia el valor de corte en absoluto. tu vuv
Aaron Roth
2
Un problema es que si agrega un borde negativo entre cada par de vértices, entonces está modificando el valor de diferentes cortes en diferentes cantidades. (Restamos, digamos, del valor de corte ). Entonces tenemos el problema de que la identidad del corte máximo en el gráfico modificado no corresponde necesariamente con el corte máximo en el gráfico original. El | S | | ˉ S | a S|S||S¯|aS
Aaron Roth
1
@Peter: en el párrafo posterior al que cité, elige tamaño suficientemente pequeño para hacer . No se puede elegir con seguridad ser suficientemente grande en un párrafo y suficientemente pequeña en la próxima! En particular, no hay forma de elegir y para asegurarse de que para todos y simultáneamente tengan . Esto se debe a que para todos implica que . 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>cdm0mnf=a(n2)d>0
Warren Schudy
2
@ Warren, eliges lo suficientemente grande como para que para todos los cortes. Esto se puede hacer eligiendo suficientemente grande. Usted entonces elige tamaño adecuado para que el corte óptimo es apenas por encima de . Lee los dos últimos párrafos de mi respuesta. dcdm<0da0
Peter Shor
11

En el artículo " Corte máximo aproximado " de S. Har-Peled, la última línea del documento menciona que la versión real ponderada de corte máximo se ha discutido en

Aproximando la norma de corte a través de la desigualdad de Grothendieck , Noga Alon y Assaf Naor, SIAM Journal on Computing, 2006.

De hecho, es un algoritmo SDP, y me parece que la relación de aproximación es 0.56, aunque no estoy seguro de si la reducción discutida en el documento es preservar la relación. Tal vez una mirada más profunda en el papel ayudará.

Hsien-Chih Chang 張顯 之
fuente
El problema en Alon-Naor es similar, pero no creo que haya una relación que mantenga la reducción. su problema es maximizar x T M y donde x , y { ± 1 } n y M es un n × n matriz. para max-cut y sus parientes cercanos es crucial que x = y
Sasho Nikolov
@SashoNikolov: para la norma de corte es irrelevante, hasta factores constantes, ya sea que exijamos x = y o no.
David
@david Conozco esta reducción, pero la afirmación que es realmente cierta es que max x | x T M x | max x , y x T M y4 max x | x T M x | donde todos los máximos están por encima de { - 1 , 1 } n , y M es simétrica con diagonal no negativa. Sin embargo, el problema max x | x T M x |puede tener un valor muy diferente de max x x T M x (que es lo que necesitamos para MaxCut). Por ejemplo, considere M = I - J , donde J es la matriz n × n todos unos. Puede ver max x x T M x es aproximadamente n / 2 , mientras que max x | x T M x | es n 2 - n .
Sasho Nikolov
6

Su problema tiene una aproximación logarítmica por reducción a un problema de programación cuadrática.

El problema de MaxQP es el problema de aproximar la forma cuadrática x T M x para una matriz n × n M , donde x varía sobre { ± 1 } n . MaxCut se puede escribir de esta forma configurando M = 12 n (we)I-12 AdondeIes la matriz de identidad yAes la matriz de adyacencia. Elalgoritmo MaxQP de Charikar y Wirthproporciona unaaproximaciónO(logn)para MaxQP siempre queMtenga una diagonal no negativa. Entonces, siempre quewe0, MaxCut con pesos negativos tenga una aproximación logarítmica.

Sasho Nikolov
fuente