Gap Redução

Na teoria da complexidade computacional, uma gap redução é uma redução de um tipo particular de problema de decisão, conhecido como problema de c-gap. Tais reduções fornecem informações sobre a dificuldade de aproximação de soluções para problemas de otimização. Em resumo, um problema de gap redução refere-se a uma redução onde o objetivo é distinguir entre os casos em que a melhor solução está acima de um limiar dos casos em que a melhor solução está abaixo de outro limiar, tal que os dois limiares tenham uma lacuna (gap) entre os dois. Gap reduções podem ser usadas para demonstrar resultados de não aproximação, como se um problema pode ser aproximado para um melhor fator de que o tamanho do gap, em seguida, o algoritmo de aproximação pode ser usado para resolver o correspondente problema da lacuna.

Problema c-gap

Definimos um problema c-gap da seguinte maneira:^[1] dado um problema de otimização (maximização ou minimização) P, o equivalente problema c-gap distingue dois casos, para uma entrada k e uma instância x do problema P:

. Aqui, a melhor solução para a instância x do problema P tem um custo, ou pontuação, abaixo de k. . Aqui, a melhor solução para a instância x do problema P tem um custo acima de c⋅k. O intervalo entre os dois limites é, portanto, c.

Note que sempre que OPT se situa entre os limites, não há nenhuma exigência de qual saída deve ser. Um algoritmo válido para o problema c-gap pode responder qualquer coisa se OPT esta no meio do intervalo. O valor de c não precisa ser constante, ela pode depender do tamanho da instância de p. Note que c-aproximar a solução para uma instância de P é pelo menos tão difícil quanto resolver o c-gap versão de P.

Pode-se definir um problema (a,b)-gap da mesma forma. A diferença é que os limites não dependem de entrada; em vez disso, o limite inferior é a e o limite superior é b.

Gap-redução de produção

Uma Gap-redução de produção é uma redução de um problema de otimização para um problema c-espaço, de modo que a solução do problema c-gap rapidamente permitiria resolver o problema de otimização. O termo gap-produção surge a partir da natureza da redução: a solução ótima do problema de otimização mapeia para o lado oposto da gap a partir de todas as outras soluções através de redução. Assim, uma lacuna(gap) é produzida entre a solução ótima e cada outra solução.

Um exemplo simples de uma gap-redução de produção é o problema do Caixeiro viajante (i.e. onde as arestas de um grafo com custos não devem satisfazer as condições de uma métrica). Podemos reduzir a partir do problema do caminho Hamiltoniano em um dado grafo G = (V, E) para este problema da seguinte forma: podemos construir um grao completo G' = (V, E'), para o problema do caixeiro viajante. Para cada aresta e ∈ G', nós deixamos o custo de percorrimento dessa aresta ser 1 se e encontra-se no grafo de G original e ∞ no caso contrário. Um caminho Hamiltoniano no gráfico original G existe, se e somente se, existe uma solução para o caixeiro-viajante com peso (|V|-1). No entanto, se tal caminho Hamiltoniano existe, então a melhor viagem do caixeiro viajante deve ter um peso de pelo menos |V|. Assim, o Caminho Hamiltoniano se reduz a |V|/(|V|-1)-gap do caixeiro-viajante.

Gap-Redução com Preservação

Uma Gap-Redução com Preservação é uma redução a partir de um c-espaço do problema para um problema c'-gap. Mais especificamente, nos é dada uma instância x de um problema A com |x| = n e o reduzimos a uma instância x' do problema B com |x'| = n'. Uma Gap-Redução com Preservação de A para B é um conjunto de funções (k(n), k'(n'), c(n), c'(n')) tal que

Para problemas de minimização:

OPT_UM(x) ≤ k ⇒ OPT_B(x') ≤ k', e

OPT_UM(x) ≥ c⋅k ⇒ OPT_B(x') ≥ c'⋅k'

Para problemas de maximização:

OPT_UM(x) ≥ k ⇒ OPT_B(x') ≥ k', e

OPT_UM(x) ≤ k/c ⇒ OPT_B(x') ≤ k'/c'

Se c' > c, então esta é uma redução de gap amplificado.

Exemplos

Max E3SAT

Este problema é uma forma de problema de Satisfatibilidade Booleana (SAT), onde cada cláusula contém três literais distintos e queremos maximizar o número de cláusulas satisfeitas.^[1]

Håstad mostrou que a versão (1/2+ε, 1-ε)-gap de um problema semelhante, MAX E3-X(N)OR-SAT é NP-difícil.^[2] O problema MAX E3-X(N)OR-SAT é uma forma de SAT onde cada cláusula é o XOR de três literais distintos, exatamente um literal de cada cláusula é negado. Podemos reduzir de MAX E3-X(N)OR-SAT para MAX E3SAT da seguinte forma:

Uma cláusula x_i ⊕ x_j ⊕ x_k = 0 é convertida para (x_i ∨ x_j ∨ x_k) ∧ (x_i ∨ x_j ∨ x_k) ∧ (x_i ∨ x_j ∨ x_k) ∧ (x_i ∨ x_j ∨ x_k)

Se uma cláusula não estiver satisfeita na instância original de MAX E3-X(N)OR-SAT, então, no máximo, três das quatro cláusulas correspondentes em nossa instância MAX E3SAT pode ser satisfeita. Usando um argumento de lacuna, segue-se que uma instância SIM do problema tem pelo menos uma fração (1-ε) das cláusulas satisfeitas, enquanto uma instância NÃO do problema tem mais de um (1/2+ε)(1) + (1/2-ε)(3/4) = (7/8 + ε/4) fração de cláusulas satisfeitas. Assim, segue-se que (7/8 + ε, 1 - ε)-gap MAX E3SAT é NP-difícil. Note que este vínculo é apertado, como uma atribuição aleatória de variáveis dá uma fração esperada de 7/8 cláusulas satisfeitas.

Rótulo de Cobertura

O problema do Rótulo de Cobertura é definido da seguinte forma: dado um grafo bipartido G = (A∪B, E), com

A = ₁ ∪ A₂ ∪ ... ∪ A_k, |A| = n e |A_i| = n/k

B = B₁ ∪ B₂ ∪ ... ∪ B_k, |B| = n e |B_i| = n/k

Podemos definir "super aresta" entre A_j e B_j se pelo menos uma aresta existe a partir de A_j para o B_j em G, e definimos a super aresta coberta, se pelo menos uma aresta de A_j para o B_j é coberta.

No versão max-rep do problema, estamos autorizados a escolher um vértice de cada A_j e cada B_j, e nosso objectivo é maximizar o número de super aresta cobertas. Na versão min-rep, necessitamos cobrir todos as super arestas no grafo, de modo a minimizar o número de vértices selecionados. Manurangsi e Moshkovitz mostram que a versão (S(n^1/4), 1)-gap de ambos os problemas é solúvel em tempo polinomial.^[3]

Veja também

Referências

↑ ^a ^b Demaine, Erik (outono de 2014). «Algorithmic Lower Bounds: Fun with Hardness Proofs Lecture 12 Notes» (PDF)
↑ Johan, Hastad (julho de 2001). «Some Optimal Inapproximability Results». J. ACM. ACM
↑ Manurangsi, Pasin; Moshkovitz, Dana (2013). «Improved Approximation Algorithms for Projection Games». ESA 2013. ESA. pp. 683–694 Em falta ou vazio |url= (ajuda)

[d-1] Demaine, Erik (outono de 2014). «Algorithmic Lower Bounds: Fun with Hardness Proofs Lecture 12 Notes» (PDF)

[2] Johan, Hastad (julho de 2001). «Some Optimal Inapproximability Results». J. ACM. ACM

[3] Manurangsi, Pasin; Moshkovitz, Dana (2013). «Improved Approximation Algorithms for Projection Games». ESA 2013. ESA. pp. 683–694 Em falta ou vazio |url= (ajuda)

[1]

[2]

[3]