Mittr6

Tema 5: Problemas de Optimización
Serafín Moral
Modelos de Informática Teórica - Universidad de Granada

Serafín Moral

Tema 5: Problemas de Optimización

Contenido

Problemas de Optimización
Algoritmos ǫ-aproximados
Análisis de problemas: cubrimiento por vértices, viajante
de comercio, corte máximo, mochila, satisfacción máxima.
Esquema de aproximación polinómico.
Clase NPO y PO
Clases APX,PTAS y FPTAS
Algoritmos pseudo-polinómicos
L-reducción
Problemas completos

Serafín Moral

Tema 5: Problemas de Optimización

Bibliografía

G. Ausiello, P. Creszendi et al. (1999) C omplexity and
Approximation. Springer-Verlag, Berlin.
A Compendium of NP Optimization Problems.
http://www.nada.kth.se/theory/compendium

Serafín Moral

Tema 5: Problemas de Optimización

Problemas de OptimizaciónProblema de Optimización (minimización)
Tenemos unos datos x.
Estos datos tienen asociados un conjunto de soluciones
factibles F (x) .
∀s ∈ F (x) tenemos una función C(s) que evalúa el coste de
esta solución.
El problema es encontar un elemento s∗ tal que
C(s∗ ) = min C(s)
s∈F (x)

Este problema se conoce cómo la versión constructiva del
problema de optimización.
Si sólo se trata de calcular C(s∗ ),tendremos la versión de
evaluación.
En general, son de dificultad similar.
Serafín Moral

Tema 5: Problemas de Optimización

El Problema del Cubrimiento por Vértices

Ejemplo
Datos: un grafo G no dirigido.
Soluciones factibles F (G): conjunto de los cubrimientos
por vértices de G el conjunto de todos los subconjuntos de
vértices A tales que toda arista tiene, al menos un extremo
en A.
Coste de unasolución factible A: su número de vértices.
Queremos encontrar el cubrimiento por vértices con un número
menor de vértices.

Serafín Moral

Tema 5: Problemas de Optimización

Problemas de Maximización

Problemas de Optimización: Maximización
Algunas veces, en vez de tener una función de coste, tenemos
una función de albluebeneficio B y tratamos de maximizarla.
Cada ejemplo x, tiene asociado unconjunto de soluciones
factibles F (x) .
∀s ∈ F (x) tenemos una función B(s) que evalúa el beneficio
de esta solución.
El problema es encontar un elemento s∗ tal que
B(s∗ ) = maxs∈F (x) B(s)

Serafín Moral

Tema 5: Problemas de Optimización

Características
Estos problemas suelen ser equivalentes bajo reducción
Turing a los problemas de decisión asociados (ver la
reducción del problema del viajantede comercio en el
tema del cálculo de funciones).
En este tema no nos vamos a preocupar de resolverlos de
forma exacta.
Vamos a ver problemas que son de similar dificultad
cuando se resuelven de forma exacta, son bastante
diferentes cuando intentamos aproximarlos: unos no se
pueden aproximar con ningún error; otros se pueden
aproximar con algún error, pero no con errores muy
pequeños; y otros sepueden aproximar con errores
arbritrariamente pequeños.

Serafín Moral

Tema 5: Problemas de Optimización

Algoritmos ǫ-aproximados
Definición
Se 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 Minimización:
c(M(x)) − OPT (x)
≤ǫ
c(M(x))
Equivalente a:

1
C(M(x))
≥
1−ǫ
OPT (x)
Serafín Moral

Tema 5:Problemas de Optimización

Problemas de Maximización

OPT (x) − c(M(x))
≤ǫ
OPT (x)
Equivalente a:
1
OPT (x)
≥
1−ǫ
C(M(x))

Serafín Moral

Tema 5: Problemas de Optimización

Razón de Eficacia
Actualmente, se suele emplear más la razón de eficacia .
1
Este valor es: δ = 1−ǫ
, donde ǫ es el grado de aproximación.
Epsilon se puede obtener como ǫ = δ−1
δ
Razón de eficacia (maximización)
Un problemade maximización tiene una razón δ si y solo si
δ≥

OPT (x)
C(M(x))

Razón de eficacia (minimización)
Un problema de minimización tiene una razón δ si y solo si
δ≥

C(M(x))
OPT (x)

Serafín Moral

Tema 5: Problemas de Optimización

Umbral de Aproximación

Umbral de Aproximación: Ínfimo de la razón de eficacia
mediante algoritmos polinómicos.
δ

1

Umbral

Serafín Moral

∞

Tema 5: Problemas de...