tata

A menos que NP=P, los problemas NP-hard no tienen algoritmos polinomiales por lo que un algoritmo que los resuelva en forma exacta puede tardar un tiempo prohibitivo. Así que debemos conformarnos con algoritmos polinomiales que den soluciones aproximadas. Existen dos categorías de tales algoritmos: algoritmos de aproximación y algoritmos heurísticos. En esta sección tratamos los primeros.Indiquemos con A un algoritmo de tiempo polinomial aplicado a un problema de minimización NP-hard que obtiene un valor A(x) aproximado del óptimo para cada instance x del problema. Sea Opt(x) el valor óptimo. Estamos interesados en acotar el error relativo de A(x). Decimos que el problema es -aproximable si existe >0 tal que para cualquier instance x del problema:
or A(x)(1+) opt(x) (1)Escribiremos tambien:

A(x) k opt(x) (k=1+) (1)

En el caso que se trata de un problema de maximización escribiremos:

A(x) k opt(x) donde k0.
2) Se puede satisfacer la desigualdad (1) para cualquier >0 prefijado.
3) No se puede acotar el error en la forma (1). Decimos que el problema no es aproximable.

Cuando se satisface (1) decimos que el problema es k-aproximable.
Elresto de esta sección es una serie de ejemplos.

1. Job Scheduling
Consideremos m máquinas iguales y n jobs que requieren pi (=1,2,...,n) tiempo en cualquiera de las m máquinas. Se trata de asignar los jobs a las máquinas de forma que el tiempo total para hacer todos los jobs sea mínimo. Este problema es NP-hard (lo demostramos para m=2). El algoritmo aproximado es el siguiente. Tenemos a losjobs en una lista ordenados de cualquier manera. Cada vez que una máquina queda disponible le asignamos el primer job de la lista. Sea opt(x) el mínimo tiempo para realizar todos los jobs usando este algoritmo. El caso mas favorable sería que ninguna máquina quedara parada como indica la figura.




De donde deducimos una cota inferior
(ipi)/m  opt(x)
Además para cualquier i es obvio quepi opt(x)
Por otra parte sea sk el instante cuando se inicia el último job y A(x) el instante que termina.





Observamos que antes del instante sk todas las máquinas deben estár funcionando de donde deducimos
sk(ik pi)/m
De donde
A(x)=sk+pk (ik pi)/m + pk= (i pi)/m + (1- 1/m)pk  opt(x) + (1-1/m)opt(x)
A(x) (2-1/m)opt(x)
De manera que este algoritmo es (2-1/m)–aproximable.2. Bin packing
a1,...,an son números no negativos que no superan a 1. Imaginemos a los ai como los pesos de items a cargar en camiones y que el limite de peso de un camión es 1. El problema consiste en cargar los n items en un mínimo número de camiones.

El siguiente algoritmo aproximado se llama first fit. Cargamos los items a1, a2,... en los camiones B1,B2.... El item ai se carga en elprimer Bk donde quepa.
Llamemos level(Bk) al peso que contiene el camión Bk.
Deduciremos una acotación del tipo (1). Primero, advirtamos la cota
a1+...+anopt(x)
Segundo, observemos que no puede haber dos camiones no vacíos que tengan level 1/2 porque pasaríamos parte de carga de uno a otro.
De manera que si cargamos en total k camiones debemos tener
level(Bi)>1/2 para todo i excepto uncamion a lo sumo 2 level(Bi)>1 2(a1+...+an)> k-1+. Como k-1+=k  2a1+...+an>k
2opt(x)>A(x)
Asi este algoritmo es 2-aproximable.

3. node cover
Se trata de hallar un mínimo conjunto C* de vertices de un grafo G tal que toda rama de G sea incidente en un vértice de C*.
Damos 2 ejemplos. El primero es 2-aproximable. En cambio, para el segundo no existe k tal que sea k-aproximable.Algoritmo 1
C=vacío
While there is an edge (u,v) add u and v to C and delete u and v from G.
End
Demostración que el algoritmo es 2-aproximable:
Sea C* un minimo cover.
Observemos que C/2 es el número de ramas elegidas por el algoritmo. Ademas estas ramas son disjuntas. Uno de sus vertices por lo menos pertenece a C*. Asi que C*  C/2  C2C*

Ejemplo de un algoritmo cuyo...