Caixeiro Viajante
Problema: Dado um grafo G=(V,E), encontrar o Circuito
Hamiltoniano de tamanho mínimo.
Teorema: A menos que P=NP, não existe algoritmo aproximativo polinomial para o TSP para qualquer 
>=1.
Prova: Suponha que exista um algoritmo -aproximativo
polinomial A para algum >1. Vamos mostrar então
que é possível encontrar um ciclo Hamiltoniano em
tempo polinomial
Caixeiro Viajante
K
K
1
K
K
1
1
1
1
1
Instância do Ciclo
Hamiltoniano
Instância do
Caixeiro Viajante
K = 1+|V|
Caixeiro Viajante
Objetivo: Provar que o algoritmo -aproximativo polinomial
para o TSP (A) irá retornar um tour de custo |V | se e
somente se existe um ciclo Hamiltoniano em G.
Se o algoritmo retorna um ciclo de custo |V| o
Ciclo Hamiltoniano existe
Se existe um ciclo Hamiltoniano em G então A
retorna um tour (T ) de comprimento menor ou
igual a |V|.
Como o TSP não utiliza nenhuma aresta de valor maior que
|V| então ele retorna um tour de custo |V|
Caixeiro Viajante
Circuito Euleriano: Um circuito Euleriano é um passeio
fechado que visita todas as arestas do grafo uma única
vez
Teorema Um grafo G admite um circuito Euleriano se e
somente se todo vértice de G tem grau par
Caixeiro Viajante
Problema: TSP sobre grafo G=(V,E) que satisfaz a
desigualdade triangular:
d(i,j)  d(i,k) + d(k,j)
Algoritmo Tree:
– Obter a árvore geradora de peso mínimo T;
– Duplicar as arestas de T;
– Obter um circuito euleriano, usando busca em
profundidade;
– Escolher um nó inicial;
– Encontrar circuito hamiltoniano sobre o circuito euleriano,
usando “atalhos” para não repetir nós.
Caixeiro Viajante
1
Árvore geradora mínima
com arestas duplicadas
5
2
4
3
Caixeiro Viajante
1
Circuito Euleriano
5
2
4
3
Caixeiro Viajante
1
Circuito Hamiltoniano
5
2
4
3
Caixeiro Viajante
1
Circuito Hamiltoniano
5
2
4
3
Caixeiro Viajante
1
Circuito Hamiltoniano
5
2
4
3
Caixeiro Viajante
Teorema: O algoritmo Tree é 2-aproximado.
Prova: Seja OPT(I) o circuito hamiltoniano de custo mínimo.
Sabemos que custo(T)  OPT(I) e A(I)  2 custo (T)
A(I)  2 .OPT(I)
Caixeiro Viajante
Algoritmo de Christofides:
– Obter a árvore geradora de peso mínimo T;
– Encontrar o conjunto C de nós de T que têm grau ímpar;
– Encontrar o matching perfeito de custo mínimo M sobre o
o subgrafo de G induzido por C
– Seja G’ = T U M;
– Encontrar um circuito euleriano em G’ e um tour neste
circuito eliminando repetições;
Caixeiro Viajante
Caixeiro Viajante
Teorema: O algoritmo de Christofides é 3/2-aproximado.
Prova:
A(I)  c(T)+c(M) e c(T) OPT(I)
C(M1) + c(M2 ) OPT(I)
C(M)  ½.OPT(I)
A(I)  3/2.OPT(I)
OPT(I)
M1
M2
Caixeiro Viajante
Exemplo Ruim
4
2
3
1
6
n-1
n
5
(n-1)/2
Christofides
4
2
1
Ótimo, custo=n-1
3
6
n-1
n
5
(n-1)/2
2
1
n
Set Cover
• SET COVER: Dado um conjunto U de
elementos e uma coleção
F={S1, S2, . . . , Sm}
de subconjuntos de U, determinar a família
G  F de menor cardinalidade tal que a
união dos conjuntos de G é igual a U
Set Cover
• Algoritmo Guloso
– Enquanto houver algum elemento não coberto
• Escolha o conjunto ainda não selecionado que cobre o maior
número de elementos de não cobertos
Set Cover
• Análise
S: primeiro conjunto escolhido.
OPT(F’,U’): custo da solução ótima para cobrir U’ utilizando a família F’
custoGr (F,U) = 1 + custoGr(F-{S},U-S)
Lema 1. OPT(F,U)>= |U|/|S|
Lema 2. OPT(F,U)>=OPT(F-{S},U-S)
Set Cover
• Análise.
– Hipótese Indutiva. razaoGreedy(F,T)<=H|T|
para todo conjunto T com |T|<|U|, onde Hn é o
n-ésimo número harmônico
custoGr ( F ,U )
1  custoGr ( F  {S}, U  S )


OPT ( F ,U )
max{|U | / | S |, OPT ( F  {S}, U  S )}
custoGr ( F  {S}, U  S ) | S |
1


 H |U ||S |  H |U |
| U | / | S | OPT ( F  {S}, U  S )
|U |
Set Cover
• [Feig 98] A menos que P=NP não existe
um algoritmo polinomial com razão de
aproximação o(log n) para o SET-COVER
Subset Sum
• Dado um par (S,t) onde t é um inteiro
positivo e S={x1,…,xn} é um conjunto de
inteiros não negativos, encontrar S’  S
cuja soma de seus elementos seja a maior
possível mas não ultrapasse T
• O problema é NP-Completo
– Redução a partir do 3-SAT
Subset Sum
• Algoritmo Exponencial
– Seja L+x a lista obtida a partir de uma lista L,
aumentando todo elemento de L de x
unidades
– L=<1,2,5,9>  L+4 =<5,6,9,13>
Subset Sum
• Algoritmo Exponencial
1. L0{0}
2. Para i1 até n faça
2.1 Li  MergeLists(Li-1,Li-1+xi)
2.2 Remova todo elemento de Li maior que t
3. Devolva o maior elemento de Ln
Subset Sum
• Algoritmo Exponencial
– O algoritmo Exponencial retorna o
subconjunto de maior soma cuja soma não
ultrapassa T
– Para obter uma aproximação em tempo
polinomial, somas com valores próximos são
descartadas
Subset Sum
• TRIM(L, ): Esta operação remove o
máximo possível de elementos de L de
modo que a lista resultante L’satisfaz:
– Para todo x  L, existe z L’ tal que
(1-)x <= z <= x
• Todas as somas de L estão representadas
em L’ salvo uma precisão
Subset Sum
• Algoritmo Approx-SubsetSum(S,t, )
L0{0}
Para i1 até n faça
Li  MergeLists(Li-1,Li-1+xi)
Li  TRIM(Li,  / n)
Remova todo elemento de Li maior que t
Devolva z, o maior elemento de Ln
Subset Sum
Lema. Seja Pi o conjunto de todas as somas
possíveis com os i primeiros números de
S. Devemos mostrar que para todo
elemento y de Pi existe um elemento wLi
, após trimmed, tal que
(1- /n)i y <= w <= y
Subset Sum
Prova
Indução em i. A base é verdadeira.
Caso i) y – xi não pertence a Pi-1
Logo, y pertence a Pi-1. Pela hip indutiva, existe w’ em Li-1
tal que
(1-  /n)i-1 y <= w’ <= y
Como a lista Li é ‘trimmed’ existe w em Li tal que (1-  /n) w’
<= w <=w’. Logo w satisfaz a condição requerida
Subset Sum
Prova
Caso ii) y – xi pertence a Pi-1
Neste caso, existe w’ em Li-1 tal que
(1-  /n)i-1 y - xi<=(1-  /n)i-1 (y-xi)<= w’<= y-xi
Por outro laso, existe w em Li tal que
(1-  /n) (w’+xi)<= w<= w’+xi
Logo, w satisfaz as condições requeridas
Subset Sum
Teorema. Approx-SubsetSum aproxima o SubsetSum de
um fator de (1-) em tempo (n2 ln t) / 
Prova.
Seja z* a solução ótima. Pelo lema o algoritmo retorna um
z tal que
(1-/n)nz*<= z<= z*.
Como (1-/n)n>(1- ) para n>1, temos que
(1-)z*<= z<= z*.
Subset Sum
Teorema. Approx-SubsetSum aproxima o SubsetSum de
um fator de (1-) em tempo
Prova.
Depois da operação de TRIM os elementos sucesssivos de
Li , w e w’, satisfazem
w/w’< 1/(1-/n).
Logo, o número máximo de elementos de Li após o TRIM é
logt1/(1-/n) <= (n ln t) / 
MAX SAT
Entrada

n variáveis booleanas : x1,... Xn

m cláusulas : C1,... Cm

Pesos wi >= 0 para cada clausula Ci
Objetivo : Encontrar uma atribuição de verdadeiro/falso
para xi que maximize a soma dos pesos das clausulas
satisfeitas
MAX SAT
Algoritmo randomizado
Para i=1,...,n
Se random(1/2) = 1
xi  true
Senão
xi  false
Com probabilidade ½ dizemos que uma variável é
verdadeira ou falsa
MAX SAT
Teorema : O algoritmo tem aproximação ½
Prova: Considere a variável aleatória xj
xj

1, se a clausula é satisfeita

0, caso contrário
W: soma dos pesos das clausulas satisfeitas
w   wj x j
Logo,
j
E (w)  E ( w j x j )   w j E ( x j )
j
j
MAX SAT
E(xj)
= 1*Pr(xj=1) + 0*Pr(xj=0)
= Pr(clausula j ser satisfeita)
Lj : número de literais na clausula j
Obs: A clausula j não é satisfeita somente se todos literais
forem 0
Cj = (x1 v x3 v x5 v x6)
Devemos ter x1=0, x3 = 1, x5 =0 e x6 =0
Probabilidade = (1/2)4
Caso Geral=(1/2)Lj
MAX SAT
Probabilidade da clausula j ser satisfeita é 1-(1/2)Lj
Logo,


  wj 
Lj
 OPT
  1    j

E ( w)   w j 1     
2
2
j
  2  
0,5-aproximação
Obs:
w
j
j
é um limite superior
MAX SAT
O que aconteceria se toda clausula tivesse exatamente 3
literais?
  1 3  7
E ( w)   w j 1       w j
j
  2   8 j
7/8-aproximação
Hastad 97) Se MAXE3SAT tem aproximação (7/8 + )
para algum  > 0, P = NP
MAX SAT
Algoritmo 2
Mudando a probabilidade do sorteio
Seja p>= ½
Para i=1,...,n
Se random(p) = 1
xi  true
Senão
xi false
MAX SAT
Lema: Seja I uma instância do MAXSAT onde nenhuma
clausula de tamanho 1 aparece negada. Então, para
toda clausula j,
Pr[cj ser satisfeita] >= min (p,1-p2)
Prova:
Caso 1) Lj = 1. Neste caso,
Pr[Cj é satisfeita] = p
Caso 2) Lj >= 2.
Pr[Cj não satisfeita] <= pLj
MAX SAT
Pr[cj ser satisfeita] >= 1 - pLj >= 1 – p2
(x1 v x2) como exmplo
Pr[Cj ser satisfeita] >= 1-p2
MAX SAT
Instância onde cláusula de tamanho 1 aparece negada?
Caso 1) Se existe a clausula (xi) e não existe a clausula
(xi), podemos fazer com que xi = true com
probabilidade 1-p. Recaimos no caso anterior
(equivalente a substituir xi por zi)
MAX SAT
Instância onde cláusula de tamanho 1 aparece negada?
Caso 2) Existe a clausula ( xi) e a clausula (xi). Neste
caso uma das duas não são satisfeitas. Dessa forma
podemos melhorar o limite superior.
Se ci=xj e ci’=  xj, retiramos min{wi,wi’} do limite
superior.
Neste
caso,
devemos
sortear
com
probabilidade a clausula de maior peso.
maior
MAX SAT
A: cláusulas cujo peso é retirado do limite superior segundo o caso 2
B: cláusulas complementares a A
Exemplo:
Clausulas: (x1 v x2 v x3) , (x4) , (x4) , (x2 v x3),
Pesos :(2, 3,5,4)
A = {(x4)} e B = {( x4)}
2
w
min{
p
,
1

p
}  p   wi
 i
E[ A lg] iA B

OPT
iB
w w
iA B
i
iB
i
 min{p,1  p 2 }
MAX SAT
Maximizando p, temos p=0.618
MAX SAT
Modele MAXSAT como PI
max  w j z j
j
s.a
 y   (1  y )  z
iI j
j
iI j
j
j
0<= zj <= 1
yi {0,1}
Ij+ : conjunto das variáveis que aparecem não-negadas em Cj
Ij- : conjunto das variáveis que aparecem negadas em Cj
MAX SAT
Exemplo (x1 v x2 v  x3) , ( x2 v  x3)
Max w1z1 + w2z2
s.a
y1 + y2 + (1 - y3) >= z1
(1 - y2)+ (1 - y3) >= z2
yi  {0,1}
0 <= zi <= 1
Resolva a relaxação linear
yi {0,1} é substituído por 0 <= y <= 1
MAX SAT
y* : solução da relaxação linear
Para i=1,...,n
Se random(y*) = 1
xi  true
Senão
xi  false
MAX SAT
Fato 1) (Desigualdade das Médias)
Seja a1,..., ak reais não negativo,então:
k
 k 
  ai 
a1a2    ak   i 1 
 k 




Fato 2) Se f é côncava em [l,v], f(l) >= al+b e f(v) >= av+b, então
f(x) >= ax + b em [l,v]
MAX SAT
Teorema : O algoritmo tem aproximação (1-1/e) @ 0,632
Prova : Considere a clausula Cj da forma:
k

* 
x1 v x2 v ... v xk
k  y i 
k
*
i 1


1

(
1

y
)

1


i
Pr(Cj é satisfeita) =


k
i 1




k
*
y
Como y* é viável,  i  zi
k
i 1

 k   y *i
i 1
1 

k


k
k


k
* k




k

z
1


j
  1 
  1  1    z *j
 k 

k  
 




MAX SAT
A última desigualdade segue do fato 2, já que
Zj*=0  1 – (1 – (Zj* / k ) ) k = 0
Zj*=1  1 – (1 – (Zj* / k ) ) k = 1-(1-1/k)k
e
1 – (1 - (Zj* / k ) )k é côncava
Sendo que este resultado vale para qualquer cláusula.
MAX SAT
E (w)   w j  Pr(clausula_ j _ é _ satisfeita)
j
  1 k 
 min1  1      w j z * j
k
  k   j
  1 k 
 1
 min1  1     OPT  1  OPT , já que lim(1-1/x)x converge
k
 e
para 1/e.
  k  