Clase28

PAII-28: algoritmos aproximados
Dr. J.B. Hayet
´ ´ CENTRO DE INVESTIGACION EN MATEMATICAS

Mayo 2008

, J.B. Hayet Programaci´n, Mayo 2008 o 1 / 40

Outline

1

Aproximaci´n o

, J.B. Hayet Programaci´n, Mayo 2008 o 2 / 40

Problemas NP
Clase NP: problemas de decisi´n que pueden estar resueltos por o un algoritmo no determinista polinomial Son todos problemas implicando unexamen – exponencial – de una combinatoria, en que cada examen es simple (verificador polinomial) No se prob´ todav´ pero probablemente NP = P: esos o ıa, problemas son dificiles Ejemplos: camino hamiltoniano (buscar un camino entre dos nodos que pas´ por todos los nodos una y una sola vez), e negociante viajero. . .

, J.B. Hayet Programaci´n, Mayo 2008 o 3 / 40

Problemas NP

Un problema dedecisi´n p es NP − dificil ssi todo problema q o de NP se puede reducir polinomialmente en p Un problema es NP-completo ssi es NP-dificil y si esta dentro de NP Los problemas de esta clases son de los mas complicados, y no existen algoritmos polinomiales para resolverles (complejidad combinatoria)

, J.B. Hayet Programaci´n, Mayo 2008 o 4 / 40

Problemas NP

¿Qu´ hacer frente a un problema NP? esi los inputs son chicos en tama˜o, un examen exhaustivo de las n combinaciones posibles puede estar razonable puede haber casos particulares del problema para los cuales existen soluciones polinomiales! podemos buscar una casi-optimalidad a trav´s de un algoritmo e polinomial

, J.B. Hayet Programaci´n, Mayo 2008 o 5 / 40

Aproximaci´n o

Outline

1

Aproximaci´n o

, J.B. HayetProgramaci´n, Mayo 2008 o 6 / 40

Aproximaci´n o

Algoritmos aproximados

es poco probable para los problemas NP que encontremos una soluci´n eficiente o por otro lado, hay unos problemas que tenemos que tratar en muchos casos, lo que nos importa realmente es una soluci´n o no demasiado mala, que se pueda obtener eficientemente: algoritmo aproximado es importante distinguir de heur´ ıstica: enuna aproximaci´n esta o cifrada la distancia hasta el optimo

, J.B. Hayet Programaci´n, Mayo 2008 o 7 / 40

Aproximaci´n o

Algoritmos -aproximados
Supongamos que trabajamos en un problema de optimizaci´n en que o usamos, por ejemplo, una funci´n objetiva f . o sea x una soluci´n que encontramos por cierto algoritmo A o sea x ∗ una soluci´n optima (una entre otras) o se dice que A es−aproximado para el problema de optimizaci´n de f si o |f (x ∗ ) − f (x)| < |f (x ∗ )| la optimizaci´n puede ser minimizaci´n o maximizaci´n. . . o o o

, J.B. Hayet Programaci´n, Mayo 2008 o 8 / 40

Aproximaci´n o

Algoritmos ρ-aproximados
De la misma manera, se puede presentar la aproximaci´n por la o raz´n ρ (raz´n de aproximaci´n) si, para un input dado, el costo del o o o algoritmoaproximado esta dentro de la raz´n ρ del costo ´ptimo: o o max( f (x) f (x ∗ ) , )≤ρ f (x ∗ ) f (x)

notar que esta bien definido necesariamente ρ > 1 ρ = 1 ser´ un algoritmo ´ptimo, ρ >> 1 un algoritmo malo ıa o muchas veces ρ es funci´n del tama˜o del input: ρ(N) o n ρ=1+
, J.B. Hayet Programaci´n, Mayo 2008 o 9 / 40

Aproximaci´n o

Algoritmos aproximados: tipolog´ ıa
hay problemas conaproximaciones polinomiales y ρ relativamente peque˜o n para otros, lo mejor que se haya podido dise˜ar son algoritmos n polinomiales cuyo ρ crece con N para unos problemas NP, puedes encontrar una familia de algoritmos polinomiales mas y mas complejos que permiten alcanzar una raz´n de aproximaci´n mejor y mejor o o un esquema de aproximaci´n para un problema de optimizaci´n o o es un algoritmo deaproximaci´n que, ademas de los inputs del o problema, toma en entrada > 0 y que para este valor es con raz´n de aproximaci´n ρ = 1 + o o

, J.B. Hayet Programaci´n, Mayo 2008 o 10 / 40

Aproximaci´n o

Algoritmos aproximados: tipolog´ ıa

lo que nos interesa son esquemas de aproximaci´n polinomiales: o tales que para > 0 dado, el algoritmo sea polinomial en N no queremos que en un esquema...