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:
- Elija un subconjunto aleatorio de vértices S
S . - Elija un orden en los vértices y coloque con avidez cada vértice v
v en SS o ˉSS¯ para maximizar los bordes cortados hasta el momento - Realice mejoras locales: si hay algún vértice en S
S 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 12∑e∈Ew(e)
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 0
Respuestas:
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 / 17b −a u v b−a (b−a)/2 (b−a)/2 a b , 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 vu v
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 ∗ GG G∗ G∗ G
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 Tu v v −d (u,x) (v,x) x≠u,v a (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 vc G u v c−2dm m (u,v) c c+a−(n−2)d d u v G∗ u v en lados opuestos. Tenga en cuenta que estamos agregando un peso fijo a cualquier corte con y en lados opuestos.(a−(n−2)d) u v
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−(n−2)d) a f≈−0.98OPT c G u v c−0.98OPT G∗ 0.02OPT G∗ 0.01OPT G 0.99OPT G∗ u 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 1d u v d a f≈−.99OPT OPT OPT T G 2 T≤OPT≤Tff-.49T-.99T0.005Tf≈-0.98OPT12T≤OPT≤T f f −.49T −.99T a 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.005T f≈−0.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 TT f −.99T≤f≤−.49T
fuente
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
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á.
fuente
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 que∑we≥0, MaxCut con pesos negativos tenga una aproximación logarítmica.
fuente