¿Es resistente la aproximación MAX CUT?

8

El problema de optimización de CSP es resistente a la aproximación si es difícil de superar el factor de aproximación de una asignación aleatoria. Por ejemplo, MAX 3-LIN es resistente a la aproximación ya que una asignación aleatoria satisface fracción de las ecuaciones lineales, pero lograr un factor de aproximación es duro.NP1/21/2+ϵNP

MAX CUT es un fundamental completo. Se puede formular como un problema de CSP para resolver ecuaciones lineales módulo 2 ( mod 2). Una asignación aleatoria logra un factor de aproximación de (del número total de aristas ). Haglin y Venkatesan demostraron que lograr un factor de aproximación 1/2NPxi+xj=11/2|E|1/2+ϵ 1/2 es NP duro (es decir, encontrar un corte mejor que |E|/2 ). Sin embargo, Hastad mostró que MAX corte no es approximable a 16/17+ϵ factor de dentro del corte óptimo a menos queP=NP. Goemans y Williamson dieron un algoritmo de tiempo polinomial basado en SDP con un factor de aproximación de 0.878 (dentro del corte óptimo) que es óptimo suponiendo la Conjetura de juegos únicos. Me parece que expresar el factor de aproximación en relación con el número total de restricciones ( ) es más natural y coherente con la convención utilizada para el problema MAX 3-LIN.|E|

¿Por qué el factor de aproximación para MAX CUT se da en relación con el tamaño del corte óptimo en lugar del número de restricciones (# de bordes)? ¿Estoy en lo cierto al concluir que MAX CUT es resistente a la aproximación cuando el factor de aproximación es relativo al número total de restricciones ( )?|E|

Mohammad Al-Turkistany
fuente
Además, me pregunto si la versión Max 3-LIN del teorema PCP de Hastad se puede inferir (directa o indirectamente) del resultado de aproximación de Haglin y Venkatesan de MAX CUT.
Mohammad Al-Turkistany

Respuestas:

13

Si mide la aproximación como una relación entre el número de restricciones satisfechas por su algoritmo dividido por el número total de restricciones, entonces trivialmente todos los problemas de satisfacción de restricciones son incondicionalmente resistentes a la aproximación.

Por definición, un problema es resistente a la aproximación si la relación de aproximación (en el peor de los casos) de una solución aleatoria es (hasta un aditivo término) mejor posible entre las relaciones de aproximación (en el peor de los casos) logradas por todos los algoritmos de tiempo polinomiales .o(1)

Con su definición de relación de aproximación, obtiene resistencia de aproximación de Max Cut (y todos los problemas de satisfacción de restricciones) solo porque siempre puede construir instancias para las cuales la relación dada (en promedio) por una asignación aleatoria es más o menos (hasta un término) lo mismo que la proporción dada por una asignación óptima.o(1)

n(n2)=n(n1)/2n2/41/2+O(1/n)n1/2

Luca Trevisan
fuente
Gracias Luca por tu buena respuesta. No me queda claro por qué el factor de aproximación de MAX 3-LIN (mod 2) se da en relación con el número total de restricciones (# de ecuaciones lineales) en lugar del óptimo.
Mohammad Al-Turkistany
3
Los resultados negativos no son: la dureza de aproximación de Hastad es que, por cada , es NP-difícil encontrar soluciones que satisfagan más que una fracción de de las ecuaciones satisfechas por un {\ em óptimo} solución. (Sería trivial decir que no existe un algoritmo que siempre satisfaga al menos una fracción de las restricciones , piense en la instancia ). ϵ>012+ϵ12+ϵxyz=0;xyz=1
Luca Trevisan