Upload
samuel-carrasco
View
19
Download
0
Embed Size (px)
DESCRIPTION
Tema cinco de la asignatura de Modelos de Computación Avanzados de la carrera de Grado de Informática de la Universidad de Granada
Citation preview
Tema 5: Complejidad de Problemas deOptimizacin Aproximados
Serafn Moral
Modelos Avanzados de Computacin - Universidad de Granada
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Contenido
Problemas de OptimizacinAlgoritmos -aproximadosAnlisis de problemas: cubrimiento por vrtices, viajantede comercio, corte mximo, mochila, satisfaccin mxima.Esquema de aproximacin polinmico.Clase NPO y POClases APX, PTAS y FPTASAlgoritmos pseudo-polinmicosL-reduccinProblemas completos
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Bibliografa
G. Ausiello, P. Creszendi et al. (1999) Complexity andApproximation . Springer-Verlag, Berlin.A Compendium of NP Optimization Problems.http://www.nada.kth.se/theory/compendium
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Problemas de Optimizacin
Problema de Optimizacin (minimizacin)Tenemos unos datos x .Estos datos tienen asociados un conjunto de solucionesfactibles F (x) .s F (x) tenemos una funcin C(s) que evala el coste deesta solucin.El problema es encontar un elemento s tal que
C(s) = minsF (x)
C(s)
Este problema se conoce cmo la versin constructiva delproblema de optimizacin.Si slo se trata de calcular C(s), tendremos la versin deevaluacin.En general, son de dificultad similar.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
El Problema del Cubrimiento por Vrtices
EjemploDatos: un grafo G no dirigido.Soluciones factibles F (G): conjunto de los cubrimientospor vrtices de G el conjunto de todos los subconjuntos devrtices A tales que toda arista tiene, al menos un extremoen A.Coste de una solucin factible A: su nmero de vrtices.
Queremos encontrar el cubrimiento por vrtices con un nmeromenor de vrtices.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Problemas de Maximizacin
Problemas de Optimizacin: MaximizacinAlgunas veces, en vez de tener una funcin de coste, tenemosuna funcin de albluebeneficio B y tratamos de maximizarla.Cada ejemplo x , tiene asociado un conjunto de solucionesfactibles F (x) .s F (x) tenemos una funcin B(s) que evala el beneficiode esta solucin.El problema es encontar un elemento s tal que
B(s) = maxsF (x)B(s)
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Caractersticas
Estos problemas suelen ser equivalentes bajo reduccinTuring a los problemas de decisin asociados (ver lareduccin del problema del viajante de comercio en eltema del clculo de funciones) cuando el problema dedecisin es NP-completo.En este tema no nos vamos a preocupar de resolverlos deforma exacta.Vamos a ver problemas que son de similar dificultadcuando se resuelven de forma exacta, son bastantediferentes cuando intentamos aproximarlos: unos no sepueden aproximar con ningn error; otros se puedenaproximar con algn error, pero no con errores muypequeos; y otros se pueden aproximar con erroresarbritrariamente pequeos.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Algoritmos -aproximados
DefinicinSe dice que M es un algoritmo -aproximado sii para todo x ,calcula M(x) F (x) tal que
|c(M(x)) OPT (x)|max{OPT (x), c(M(x))}
En Problemas de Minimizacin:c(M(x)) OPT (x)
c(M(x))
Equivalente a: 11
C(M(x))OPT (x)
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Problemas de Maximizacin
OPT (x) c(M(x))OPT (x)
Equivalente a:
11
OPT (x)C(M(x))
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Razn de EficaciaActualmente, se suele emplear ms la razn de eficacia .Este valor es: = 11 , donde es el grado de aproximacin.Epsilon se puede obtener como = 1Razn de eficacia (maximizacin)Un problema de maximizacin tiene una razn si y solo si
OPT (x)C(M(x))
Razn de eficacia (minimizacin)Un problema de minimizacin tiene una razn si y solo si
C(M(x))OPT (x)
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Umbral de Aproximacin
Umbral de Aproximacin: nfimo de la razn de eficaciamediante algoritmos polinmicos.
1 b
Umbral
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Valor de la razn de eficacia
Una razn de 1 es equivalente a un algoritmo exacto.Puede haber problemas en los que el umbral deaproximacin sea infinito (no hay algoritmos polinmicoscon una razn de eficacia ).
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Aprox. para Cubrimiento por Vrtices
Buscamos el conjunto C con un nmero mnimo de nodos quesea un cubrimiento para G = (V ,E).Algoritmo Aproximado:
C = Mientras haya aristas en G
Elegir un nodo de G con grado maximo Aadir el nodo a C Borrar de G ese nodo y todos sus enlaces
Este no es un algoritmo -aproximado ningn valor de .El error puede llegar a ser de orden log(n).
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Cubrimiento por Vrtices
c1
c2
c3
c4
c5
b1
b2
b3
b4
b5
a1
a2
a3La heurstica podra elegir los nodos ro-jos.Con los verdes sera suficiente
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Se puede equivocar ms
c1
c2
c3
c4
c5
c6
b1
b2
b3
b4
b5
b6
a1
a2
a3
a4
a5
a6
a7
En los nodos de la derecha se sigue el sigu-iente procedimiento: Para i desde 2 a 5 (unomenos que los nodos del centro) Se devidenlos nodos del centro de i en i y cada grupode i se conecta con un nodo distinto de laderecha.Si un grupo no est completo no se considera.El siguiente debe de cubrir los nodos que noestn cubiertos en este.Podemos elegir los rojos.Con los verdes sera suficienteRazn 13/6 > 2.Puede llegar a log(n).
n nmero de nodos centrales
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Aproximacin para Cubrimiento por Vrtices
Algoritmo 2-Aproximado:
C = Mientras haya aristas en G
Elegir una arista cualquiera de G Aadir sus dos extremos a C Borrar de G los dos nodos y todas sus aristas
Este es un algoritmo 2-aproximado : todas las aristas tienenque tener un extremos en C. De esta forma, nunca elegimosms del doble de lo necesario.Es el mejor algoritmo que se conoce. No se puede aproximarcon = 1.1659.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
El problema del Corte Mximo: CM
Datos: Un grafo no dirigido G = (V ,E).Problema: Partir V en dos conjuntos S y V S de talmanera que haya un nmero mximo de arcos entre S yV S.
El problema de decisin es NP-completo.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Un algoritmo Greedy
Comenzamos con un conjunto S arbitrario Mientras S cambie
Para cada vertice v del grafo Si el vertice esta en S
Comprobar si al quitarlo aumenta el corte En ese caso se elimina de S
Si el vertice no esta en S Comprobar si al aadirlo a S aumenta el corte En ese caso se aade a S
Este algoritmo es polinmico, ya que da como mximo |E |pasos y cada paso es polinmico.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Es un algoritmo con razn de aproximacin 2
V1 V2
V3 V4
Corte Heurstico
Corte ptimo
Sea eij , 1 i j 4 el nmero de arcos entre Vi y Vj .Para cada nodo de V1 los arcos que van a nodos de V1 y V2son menos que los que van a V3 y V4:x1 V1,arc(x1,V1) + arc(x1,V2) arc(x1,V3) + arc(x1,V4).Sumando la desigualdad anterior en todos los nodos de V1obtenemos: 2e11 + e12 e13 + e14y, por tanto, e12 e13 + e14.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Corte Mximo
Repitiendo lo anterior para V1,V2,V3,V4, obtenemose12 e13 + e14, e12 e23 + e24,e34 e23 + e13, e34 e14 + e24
Sumando y dividiendo por dos se obtienee12 + e34 e14 + e23 + e13 + e24
Tambin es obvio que e14 + e23 e14 + e23 + e13 + e24.Sumando, las dos ltimas desigualdades obtenemos:
e12 + e34 + e14 + e23 2.(e14 + e23 + e13 + e24)
Lo que nos disce que nuestro algoritmo heurstico, al menos,obtiene la mitad de arcos del ptimo: La razn de aproximacines 2.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Satisfaccin Mxima: GMAXSAT
DATOS: Tenemos m frmulas booleanas: {1, . . . , m} queinvolucran a n variables.Problema: Queremos encontrar una asignacin de valoresde verdad que maximice el nmero de frmulas ciertas.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Algoritmo Aproximado
Para una asignacin de valores de verdad al azar,calculamos la p robabilidad de que i sea cierta:
P(i) =ti2k
donde ti es el nmero de asignaciones a las variablesque hacen que i sea cierta y k el nmero de variablesde la frmula.Para una asignacin al azar de valores de verdad elnmero esperado de frmulas que se satisfacen es
P() =m
i=1P(i)
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Algoritmo Aproximado
Si seleccionamos una variable x1, tenemos que
P() = 1/2 (P([x1 = verdadero]) + P([x1 = falso]))
donde [x1 = verdadero], [x1 = falso] son losconjuntos de frmulas que se obtienen a partir de lasoriginales, substituyendo x1 por verdadero ( x1 falso) yx1 por falso ( x1 verdadero) respectivamente.Elegimos x1 = verdadero siP([x1 = verdadero]) P([x1 = falso]) y x1 = falso encaso contrario.Si x1 es verdadero repetimos lo mismo para el resto delas variables con [x1 = verdadero] y si lo hacemos falsotrabajamos con [x1 = falso].
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Ejemplo
p q, p r q, p, p sq s, r s q, s, r p s
Num. Esp. = 3/4+7/8+1/2+3/4+3/4+7/8+1/2+7/8
= 5+7/8
V , r q, V , sq s, r s q, s, V
Num. Esp. = 1+3/4+1+1/2+3/4+7/8+1/2+1=6+3/8
q, V , F , Vq s, r s q, s, r s
Num. Esp. = 1/2+1+0+1+3/4+7/8+1/2+3/4= 5+3/8
p Verd.
p Fals.
Hacemos p verdadero
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Ejemplo
p q, p r q, p, p sq s, r s q, s, r p s
Num. Esp. = 3/4+7/8+1/2+3/4+3/4+7/8+1/2+7/8
= 5+7/8
V , r q, V , sq s, r s q, s, V
Num. Esp. = 1+3/4+1+1/2+3/4+7/8+1/2+1=6+3/8
q, V , F , Vq s, r s q, s, r s
Num. Esp. = 1/2+1+0+1+3/4+7/8+1/2+3/4= 5+3/8
p Verd.
p Fals.
Hacemos p verdadero
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Propiedades del Algoritmo
De esta manera, el valor esperado del frmulas que sesatisfacen nunca decrece.Cuando llegamos al final (todas las variables tienen suvalor de verdad), el numero esperado es el nmero exactode frmulas que se satisfacen, que es al menos el nmerooriginal P().El ptimo del problema es menor o igual que el nmero defrmulas i para las que P(i) > 0, lo que denotamoscomo #{i : P(i) > 0}.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Razn de aproximacin
La razn de aproximacin es:
OPT (x)APROX(x) =
#{i : P(i ) > 0}APROX(x)
#{i : P(i) > 0}P(1) + . . .+ P(m)
1mn {P(i) : P(i ) > 0}
Este es un algoritmo delta-aproximado con = 1mn {P(i ) : P(i )>0} .
Para frmulas con k variables como mximo es -aproximado = 2k .
Para clusulas es un algoritmo con razn 2.Para clusulas con k literales distintos es = 11(2k ) .
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
El Problema del Viajante de Comercio
S i P 6= NP el problema del viajante de comercion no tiene unalgoritmo con umbral polinmico.Supongamos que existe un algoritmo delta-aproximadopolinmico para el problema del viajante de comercio (
Viajante de Comercio
Si el algoritmo encuentra un circuito de coste |V |, existe un circuitohamiltoniano en G.Si el algoritmo aproximado no encuentra un circuito de coste |V |,devolver un circuito de coste mayor de |V |., entonces comoCoste Circuito
Optimo deducimos
Optimo Coste Circuito
> |V |Como consecuencia, Optimo > |V | y el ptimo tiene un arco que noes de G y, por tanto, G no tiene un circuito hamiltoniano.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
El problema de la Mochila
Pesos: w1, . . . ,wn Valores: v1, . . . , vnPeso lmite: WProblema: Encontrar S {1, . . . ,n} tal que iS wi W y
iS vi sea mximo.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Algoritmo Pseudo-Polinmico
Sea V = max {v1, . . . , vn}Para i = 0,1, . . . ,n y 0 v nV calculamos:W (i , v): Mnimo peso que se puede conseguir eligiendo itemsentre los i primeros de valor v exactamente.Se calcula con:W (i + 1, v) = mn {W (i , v),W (i , v vi+1) + wi+1}Estos valores resuelven el problema. Complejidad O(n2V ). EsPseudo-polinmico.Cuando se ha calculado W (n, v) es fcil calcular el ptimo.Comparamos, desde i = nV hasta i = 0 los valores W (n, i)con el lmite W . El primer i para el que W (n, i) W es elptimo del problema.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Algoritmo Aproximado
Dado un ejemplo I = (w1, . . . ,wn,W , v1, . . . , vn) consideramosI = (wi , . . . ,wn,W , v 1, . . . , v n)
donde v i = 2b[ vi
2b].
(Los b bits menos significativos se reemplazan por 0).Entonces aplicamos el algoritmo pseudo-polinmico. Estetendr una complejidad en este caso de O
(n2V2b
).
Se obtiene un algoritmo -aproximado, haciendob =
[log( (1).Vn )
].
Sea S el conjunto ptimo del problema original y S el queobtenemos en el algoritmo aproximado. Tenemos que:
iS vi
iS vi
iS vi
iS v
i
iS(vi 2b)
(
iS vi) n.2b
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Algoritmo Aproximado
iS
vi iS
vi (iS
vi) n.2b
Por tanto, la diferencia entre el ptimo y lo que calculamos esmenor o igual a n.2b.Si b =
[log( (1).Vn )
],y si el valor es, al menos, V (todos los
items caben) tenemos queV (S)V (S)
V (S) + n2bV (S) 1 +
V .( 1)V =
Es decir es un algoritmo -aproximado.La complejidad es O
(n2V2b
), que para b =
[log( (1).Vn )
], se
convierte en O(n3/( 1)).
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Esquema de Aproximacin Polinmico
Un problema de optimizacin tiene un esquema deaproximacin polinmico si existe un algoritmo que para cada > 1 y cada ejemplo x de , devuelve una aproximacin degrado del ptimo de x , en tiempo polinmico en funcin de|x | (el polinomio puede depender de ).Si la dependencia de se puede expresar como un polinomioen (1/( 1)), se dice que es un esquema de aproximacinpolinmico total .
El problema de la mochila tiene un esquema de aproximacinpolinmico total
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Conjunto IndependienteTeoremaSi existe un algoritmo 0-aproximado polinmico con 0 < para el mximo conjunto independiente, entonces existe un es-quema de aproximacin polinmico.Si G = (V ,E) es un grafo consideremos el grafoG2 = (V V ,E ) donde
E = {((u,u), (v , v )) : ((u, v) E) (u = v (u, v ) E)}1
2
3
G (1,1)
(2,1)
(3,1)
(1,2)
(2,2)
(3,2)
(1,3)
(2,3)
(3,3)
G2
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Relacin entre G y G2
Resultado IntermedioG tiene un conjunto independiente de tamao k si y solo si G2tiene un conjunto independiente de tamao k2.
Si S es un conjunto independiente de G entonces S Ses un conjunto independiente de G2.Si G2 tiene un conjunto independiente H de tamao k2,entonces H1 = {u V : v , (u, v) H} yHu = {v V : (u, v) H} para todo u V , sonconjuntos independientes de G.Si H es de tamao k2, al menos uno de estos conjuntostiene que tener tamao k .
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Demostracin
TeoremaSi existe un algoritmo 0-aproximado polinmico con 0 < para el mximo conjunto independiente, entonces existe un es-quema de aproximacin polinmico.Supongamos un algoritmo 0-aproximado de orden O(nl ).Si aplicamos el algoritmo a G2, entonces ser de ordenO(n2l).Si k es el tamao ptimo de un conjunto independiente en G,el tamao del ptimo en G2 ser de tamao k2 y el quecalcule el algoritmo aproximado verificar:
k2tam(H) 0
o equivalentemente
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Demostracin
Sea H un conjunto de tamao mximo elegido entre H1 y Hu( u V ) que se definen como anteriormente.Este es un conjunto independiente y de tamao mayor o igualque la raiz cuadrada del tamao de H.Por tanto:
ktam(H )
0
Es decir hemos conseguido con una complejidad de O(n2l) unalgoritmo 1-aproximado donde 1 =
0.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Demostracin
1 =0
Tenemos que 1 < 0. Si esto mismo lo repetimos r veces,obtenemos un algoritmo r -aproximado donde r = 2r
0.
Como este valor converge hacia 1 cuando r converge ainfinito, siempre podemos encontrar algoritmos -aproximadospolinmicos para cualquier valor de tan cerca de 1 comoqueramos.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
La clase NPO
Definicin NPOUn problema de optimizacin est en NPO si y solo si secumplen las siguientes condiciones:
1 El conjunto de entradas correctas se puede reconocer entiempo polinmico.
2 Existe un polinomio q tal que para cada caso delproblema x , y para cada solucin factible y , tenemos que|y | q(|x |), y adems para cada |y | q(|x |) es decidibleen tiempo polinmico si es una solucin factible delproblema.
3 La funcin de costo se puede calcular en tiempopolinmico.
Ejemplo: El cubrimiento mnimo por vrtices.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Problemas Polinmicos de Optimizacin
La clase POUn problema de optimizacin est en la clase PO si est enNPO y existe un algoritmo polinmico tal que para cada casodel problema x existe un algoritmo polinmica que calcula lasolucin ptima y su coste.
Ejemplo: La distancia mnima en grafos.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Optimizacin Decisin
Dado un problema de optimizacin (minimizacin omaximizacin), siempre podemos asociarle un problema dedecisin: por ejemplo para un problema de minizacin, se dauna cota K y se pregunta si existe una solucin factible decosto menor o igual a K .
TeoremaPara cualquier problema de optimizacin de NPO su correspon-diente problema de decisin est en NP.
TeoremaSi P 6= NP entonces PO 6= NPO.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
La clase APX
Definicin: Clase APXLa clase APX es la clase de todos los problemas tales queadmiten un algoritmo -aproximado para
La clase APX
Definicin: Clase APXLa clase APX es la clase de todos los problemas tales queadmiten un algoritmo -aproximado para
La clase APX
Definicin: Clase APXLa clase APX es la clase de todos los problemas tales queadmiten un algoritmo -aproximado para
La clase APX
Definicin: Clase APXLa clase APX es la clase de todos los problemas tales queadmiten un algoritmo -aproximado para
La clase PTAS
Definicin de PTASEs la clase de problemas con un esquema de aproximacinpolinmico.
Ejemplo: Un problema de PTASel problema de la mochila en el que puede haber tantas copiascomo se quiera de cada objeto.
Ejemplo: Problemas de APX que no est en PTAS (si P 6= NP)El corte mximo o el cubrimiento mnimo.
TeoremaEn grafos planares, el cubrimiento mnimo est en PTAS.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
La Clase FPTAS
Definicin: Problemas con un esquema de aproximacinpolinmico total (FPTAS)Para cada ejemplo x del problema , y todo nmero racional > 1, el algoritmo devuelve para la entrada (x , ) una solucin-aproximada que es polinmico en |x | y (1/( 1)).
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Problemas de FPTAS
Definicin: Problemas acotados polinmicamenteUn problema de optimizacin est acotado polinmicamente siy solo si existe un polinomio p tal que para todo ejemplo x ypara toda solucin factible y de x , entonces
c(x , y) p(|x |)
donde c(x , y) es el coste de la solucin y .
EjemploEl problema del viajante de comercio no est acotado polinmi-camente. El del cubrimiento mnimo por vrtices si lo est.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
FPTAS y PTAS
TeoremaNo existe un problema NP-difcil acotado polinmicamente conun esquema de aproximacin polinmico total.
CorolarioSi P 6= NP entonces PTAS 6= FPTAS
EjemploEl mximo conjunto independiente para grafos planares estaraen PTAS - FPTAS.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Problemas Pseudo-polinmicos
En el problema del corte mximo la dificultad est en suestructural combinatoria: no hay nmeros, slo un grafocon sus vrtices y arcos.El problema de la mochila puede resolverse porprogramacin dinmica en tiempo O(n2pmax) donde pmaxes el entero de tamao mximo que aparece en elproblema. Eso no implica que el problema sea polinmico,pero su complejidad se debe al tamao de los nmerosque aparecen.
Problemas Pseudo-polinmicosLos problemas que tienen un algoritmo tal que para cadaejemplo del problema x encuentra la respuesta correcta en untiempo que depende polinmicamente de |x | y del enteromayor que aparezca en la especificacin de x se dice que sonPseudo-Polinmicos.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Problemas NP-completos y pseudo-polin.TeoremaSi es un problema que est en FPTAS , y si existe un poli-nomio p tal que para cada ejemplo x , el coste ptimo del prob-lema c(x) verifica:
c(x) p(|x |,max(x))
donde max(x) es el entero mayor que aparece en x , entoncesel problema es pseudo-polinmico .DemostracinBasta con llamar al esquema de aproximacin polinmico totalpara el problema x y para la aproximacin
=p(|x |,max (x)) + 2p(|x |,max (x)) + 1
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Demostracin
c(x) p(|x|,max(x))
Demostracin
=p(|x|,max (x)) + 2p(|x|,max (x)) + 1
Entonces el algoritmo es exacto, ya que si CA(x) es el coste aproximadoCA(x)c(c) =
p(|x|,max (x))+2p(|x|,max (x))+1
Si CA(x) fuese c(x) + 1, como c(x) p(|x|,max(x)), tendramos queCA(x)c(c) > =
p(|x|,max (x))+2p(|x|,max (x))+1
Luego CA(x) = c(x)Por otra parte, el esquema de aproximacin polinmico total trabaja en tiempoO(q(|x|, 1/(1 ))) donde q es un polinomio,Como = p(|x|,max (x))+2p(|x|,max (x))+11/(1) = p(|x|,max (x))+1, por lo tanto el agoritmo tiene una complejidad de orden:O(q(|x|, p(|x|,max (x)) + 1)) que es un polinomio en la longitud de la entrada y elentero ms grande.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Demostracin
c(x) p(|x|,max(x))
Demostracin
=p(|x|,max (x)) + 2p(|x|,max (x)) + 1
Entonces el algoritmo es exacto, ya que si CA(x) es el coste aproximadoCA(x)c(c) =
p(|x|,max (x))+2p(|x|,max (x))+1
Si CA(x) fuese c(x) + 1, como c(x) p(|x|,max(x)), tendramos queCA(x)c(c) > =
p(|x|,max (x))+2p(|x|,max (x))+1
Luego CA(x) = c(x)Por otra parte, el esquema de aproximacin polinmico total trabaja en tiempoO(q(|x|, 1/(1 ))) donde q es un polinomio,Como = p(|x|,max (x))+2p(|x|,max (x))+11/(1) = p(|x|,max (x))+1, por lo tanto el agoritmo tiene una complejidad de orden:O(q(|x|, p(|x|,max (x)) + 1)) que es un polinomio en la longitud de la entrada y elentero ms grande.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Clases de Aproximacin
NPO
APX
PTAS
FPTAS
PO
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-Reduccin
ReduccinDecimos que el problema de optimizacin 1 se L-reduce alproblema 2 ( 1 L 2) si y solo siexisten dos funciones R y S espacio logartmicas y dosconstantes , > 0 tales que
Si x es un ejemplo de 1, entonces R(x) es un ejemplode 2 con OPT(R(x)) .OPT(x)
Si s es factible de R(x), entonces S(s, x) es factible dex con
|OPT(x) C(S(s, x))| .|OPT(R(x)) C(s)|
Las L-reducciones son transitivas
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-Reducciones
TeoremaSi tenemos una L-reduccin de 1 a 2, siendo estos proble-mas de minimizacin, con constantes y , entonces si existeun algoritmo -aproximado polinmico para 2 tambin existiruno 1 + ( 1) polinmico para 1.DemostracinSupongamos las funciones R y S de la L-reduccin.El algoritmo aproximado para 1 se construye de la siguienteforma ( x es un caso de este problema)
Calcular R(x)Aproximar R(x) por su algoritmo -aproximado,obteniendo sCalcular S(s) como aproximacin de x
Supongamos un problema de minimizacin.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-reducciones
DemostracinComo,
|OPT(x) C(S(s))| .|OPT(R(x)) C(s)|
C(S(s)) OPT(x) .(C(s) OPT(R(x)))
y, por tanto,
C(S(s)) .(C(s) OPT(R(x))) + OPT(x)
Tambin,C((s))OPT (R(x))
OPT (R(x)) =C((s))
OPT (R(x)) 1 1
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-reducciones
DemostracinTenemos,
C((s)) OPT (R(x))OPT (R(x)) 1
C(S(s)) .(C(s) OPT(R(x))) + OPT(x)Y ya podemos obtener la cota para el error relativo:
C(S(s))OPT (x) 1 +
C(s)OPT (R(x))OPT (x)
1 + C((s))OPT (R(x))OPT (R(x)) 1 + .( 1)
que es la cota deseada.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-ReduccionesTeoremaSi tenemos una L-reduccin de 1 a 2, siendo estos proble-mas de maximizacin, con constantes y , entonces si existeun algoritmo -aproximado polinmico para 2 tambin existiruno (1) polinmico para 1.
DemostracinSupongamos las funciones R y S de la L-reduccin.El algoritmo aproximado para 1 se construye de igual formaque en el caso de un problema de minimizacin ( x es un casode este problema)
Calcular R(x)Aproximar R(x) por su algoritmo -aproximado,obteniendo sCalcular S(s) como aproximacin de x
Supongamos ahora un problema de maximizacin.Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-reducciones
DemostracinComo,
|OPT(x) C(S(s))| .|OPT(R(x)) C(s)|
OPT(x) C(S(s)) .(OPT(R(x)) C(s))
Tambin,
OPT(R(x)) .OPT(x)
OPT (R(x))C(s)
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-reducciones
Demostracin
Obtengamos una cota para OPT (x)C(S(s))OPT (x)C(S(s))
OPT (x)OPT (x) (OPT (R(x)) C(s))
(por ser OPT(x) C(S(s)) .(OPT(R(x)) C(s)))Y por ser OPT(R(x))/ OPT(x) y f (y) = y/(y a) una funcin decreciente en y :
OPT (x)OPT (x) (OPT (R(x)) C(s))
OPT (R(X))/OPT (R(X))/ (OPT (R(x)) C(s))
Con lo queOPT (x)C(S(s))
OPT (R(X))/
OPT (R(X))/ (OPT (R(x)) C(s))=
OPT (R(X))OPT (R(X)) (OPT (R(x)) C(s))
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-reducciones
DemostracinTenemos:
OPT (x)C(S(s))
OPT (R(X))OPT (R(X)) (OPT (R(x)) C(s)) =
11 (1 C(s)/OPT (R(x)))
Al ser OPT (R(x))/C(s) , tenemos que C(s)/OPT (R(x)) 1/ y,por tanto
11 (1 C(s)/OPT (R(x)))
11 (1 1/) =
( 1)
Obeteniendo la cota: OPT (x)C(S(s)) (1)
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Ejemplo
EjemploLa reduccin del conjunto independiente al cubrimiento por no-dos no es una L-reduccin.
El ptimo del cubrimiento puede ser tan grande como se quierapara un conjunto independiente fijo.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-reduccin y PTAS
TeoremaSi tenemos una L-reduccin de 1 a 2, entonces si 2 esten PTAS, entonces 1 tambin lo est.
DemostracinSi existe un algoritmo -aproximado polinmico para 2 tam-bin existir uno 1 + (.( 1)) polinmico para 1. Cuando converge hacia 1, entonces 1 + (.( 1)) se puede hacertan cercano a 1 como se quiera.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
TeoremaSi tenemos una L-reduccin de 1 a 2 y son problemas deminimizacin, entonces si 2 est en APX, entonces 1 tam-bin lo est.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Problemas Completos y Difciles
DefinicinDada una clase C de problemas en NPO , decimos que unproblema es C-difcil si y solo si cualquier otro problema deC es L-reducible a l. Y es C-completo si, adems, est en C.
TeoremaSi un problema NPO-completo tiene un esquema de aproxi-macin polinmico, entonces todos los problemas de NPO tam-bin lo tienen.
Un teorema anlogo se puede dar para la clase APX.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
Ejemplos
Ejemplo: Problemas NPO-completosMxima, mnima satisfaccin ponderada, mxima y mnima pro-gramacin lineal {0,1} y el problema del viajante de comercio.
Ejemplo: Problemas APX-completosSatisfaccin mxima de clusulas de longitud 3, de clusulasde longitud 2, el corte mximo, viajante de comercio con de-sigualdad triangular, mnimo cubrimiento por vrtices, mnimoconjunto de ruptura de ciclos en grafos dirigidos.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
L-Reduccin
ReduccinDecimos que el problema de optimizacin 1 se L-reduce alproblema 2 ( 1 L 2) si y solo siexisten dos funciones R y S espacio logartmicas y dosconstantes , > 0 tales que
Si x es un ejemplo de 1, entonces R(x) es un ejemplode 2 con OPT(R(x)) .OPT(x)
Si s es factible de R(x), entonces S(s, x) es factible dex con
|OPT(x) C(S(s, x))| .|OPT(R(x)) C(s)|
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
AP-Reduccin
ReduccinDecimos que el problema de optimizacin (minimizacin) 1 seAP-reduce al problema 2 (minimizacin) ( 1 AP 2) si ysolo si existen dos funciones R(x , r) y S(x , y , r) espaciologartmicas y una constante constantes > 0 tal que paratodo nmero racional r
Si x es un ejemplo de 1, entonces R(x , r) es unejemplo de 2Si s es factible de R(x), entonces S(s, x , r) es factible dex y si C(s)OPT (R(x,r)) r , entonces se verifica que:
S(s, x , r)OPT (x)) 1 + (r 1)
Si el problema es de maximizacin se invierte la fraccin.Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados
AP-reduccin
TeoremaSi tenemos una AP-reduccin de 1 a 2, entonces si 2 esten APX, entonces 1 tambin lo est.
TeoremaSi tenemos una AP-reduccin de 1 a 2, entonces si 2 esten PTAS, entonces 1 tambin lo est.
EjemploLa reduccin entre el conjunto independiente mximo y el cliquemximo que transforma un grafo en el complementario y un con-junto de vrtices en l mismo es una AP-reduccin con = 1.
Serafn Moral Tema 5: Complejidad de Problemas de Optimizacin Aproximados