A aproximação do MAX CUT é resistente?

O problema de otimização do CSP é resistente à aproximação se for difícil vencer o fator de aproximação de uma atribuição aleatória. Por exemplo, MAX 3-LIN é resistente à aproximação, pois uma atribuição aleatória satisfaz fração das equações lineares, mas alcançar o fator de aproximação é -hard.1 / 2 1 / 2 + ε N $NP$$1/2$$1/2+ \epsilon$$NP$

MAX CUT é um fundamental completo. Pode ser formulado como problema de CSP na resolução de equações lineares módulo 2 ( mod 2). Uma atribuição aleatória atinge um fator de aproximação de (do número total de arestas ). Haglin e Venkatesan provaram que alcançar um fator de aproximação é -hard (isto é, encontrar um corte melhor que ). No entanto, Hastad mostrou que o MAX CUT não é aproximado ao fator 16/17 dentro do corte ideal, a menos quex i + x j = um 1 / 2 | E | 1 / 2 + ε N P | E | / 2 16 / 17 de + ε P = N P | E $NP$$x_i + x_j= 1$$1/2$$|E|$$1/2+ \epsilon$$NP$$|E|/2$$16/17+ \epsilon$$P=NP$. Goemans e Williamson deram um algoritmo de tempo polinomial baseado em SDP com fator de aproximação de 0,878 (dentro do corte ideal), que é ideal assumindo a conjectura de jogos exclusivos. Parece-me que expressar o fator de aproximação em relação ao número total de restrições ( ) é mais natural e consistente com a convenção usada para o problema MAX 3-LIN.$|E|$

Por que o fator de aproximação para MAX CUT é fornecido em relação ao tamanho do corte ideal em vez do número de restrições (número de arestas)? Estou certo ao concluir que MAX CUT é resistente à aproximação quando o fator de aproximação é relativo ao número total de restrições ( )?$|E|$

Se você medir a aproximação como uma razão entre o número de restrições atendidas pelo seu algoritmo dividido pelo número total de restrições, trivialmente todos os problemas de satisfação das restrições serão incondicionalmente resistentes à aproximação.

Por definição, um problema é resistente à aproximação se a razão de aproximação (no pior caso) de uma solução aleatória for (até um aditivo termo) melhor possível entre as relações de aproximação (no pior caso) alcançadas por todos os algoritmos de tempo polinomial .$o(1)$

Com sua definição de taxa de aproximação, você obtém resistência de aproximação de Max Cut (e todos os problemas de satisfação de restrição) apenas porque sempre é possível construir instâncias para as quais a taxa fornecida (em média) por uma atribuição aleatória é mais ou menos (até um termo) igual à proporção dada por uma atribuição ideal.$o(1)$

$n$${n \choose 2} = n\cdot (n-1)/2$$n^2/4$$1/2 + O(1/n)$$n$$1/2$