Nociones de aproximabilidad [2010-10-26 Tue]--[2010-11-04 Thu]
Jérémy Barbay 9 Nov 201009/11/10 at 11:322010-11-09 11:32:09
Nociones de aproximabilidad (2 semanas = 4 charlas)
===================================================
Author: Jérémy Barbay
[2010-10-26 Tue]--[2010-11-04 Thu]
- problemas que son o no aproximables
Table of Contents
=================
1 Intro: Aproximación de problemas de optimización NP-dificiles
2 *$p(n)$-aproximación*: Definición
3 Ejemplo: Bin Packing (un problema que es 2-aproximable)
4 Ejemplo: Recubrimiento de Vertices (Vertex Cover)
5 Ejemplo: Vendedor viajero (Traveling Salesman)
6 Ejemplo: Vertex Cover con pesos
7 PTAS y FPTAS: Definiciones
8 Ejemplo: Problema de la mochila
1 DONE Intro: Aproximación de problemas de optimización NP-dificiles
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
- Que problemas NP dificiles conocen?
- colorisacion de grafos
- ciclo hamiltonian
- Recubrimiento de Vertices (Vertex Cover)
- Bin Packing
- Problema de la Muchila
- Vendedor viajero (Traveling Salesman)
- Que hacer cuando se necessita una solucion en tiempo
polinomial?
- Consideramos los problemas NP completos de decisión,
generalmente de optimización. Si se necesita una solucionó
en tiempo polinomial, se puede considerar una aproximación.
2 DONE *$p(n)$-aproximación*: Definición
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
* Dado un problema de minimización, un algoritmo $A$ es un
*$p(n)$-aproximación* si
$\forall n \max \frac{ C_A(x) }{ C_{OPT}(x) } \leq p(n)$
* Dado un problema de maximización, un algoritmo $A$ es un
*$p(n)$-aproximación* si
$\forall n \max \frac{ C_{OPT}(x) }{ C_A(x) } \leq p(n)$
- Notas:
1) AquÃ- consideramos la cualidad de la solución, NO la
complejidad del algoritmo. Usualmente el problema es
NP-difÃ-cil, y el algoritmo de aproximación es de
complejidad polinomial.
2) Las razones estas \geq 1 (elijamos las definiciones para
eso)
3) A veces consideramos también C_A(x)-C_{OPT}(x)
(minimización) y C_{OPT}(x)-C_A(x): eso se llama un
"esquema de aproximación polinomial" y vamos a verlo mas
tarde.
3 DONE Ejemplo: Bin Packing (un problema que es 2-aproximable)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
- DEFINICIÓN
Dado $n$ valores $x_1, \ldots, x_n$, $0\leq x_i\leq 1/2$,
cual es la menor cantidad de cajas de tamaño 1 necesarias
para empaquetarlas?
- Algoritmo "Greedy"
- Considerando los $x_i$ en orden,
- llenar la caja actual todo lo posible,
- pasar ala siguiente caja.
- Análisis
- Este algoritmo tiene complejidad lineal O(n).
- Greedy da una 2-aproximación.
- (se puede mostrar facilamente en las instancias donde el
algoritmo óptima llene completamente todas las cajas.)
- Además, hay mejores aproximaciones,
1. Best-fit tiene performance ratio de 1.7 en el peor caso
2. [Best-Fit Bin-Packing with Random Order (1997), Kenyon]
Best-fit is the best known algorithm for on-line
binpacking, in the sense that no algorithm is known to
behave better both in the worst case (when Best-fit has
performance ratio 1.7) and in the average uniform case,
with items drawn uniformly in the interval [0; 1] (then
Best-fit has expected wasted space O(n 1=2 (log n) 3=4
)). In practical applications, Best-fit appears to perform
within a few percent of optimal. In this paper, in the
spirit of previous work in computational geometry, we study
the expected performance ratio, taking the worst-case
multiset of items L, and assuming that the elements of L
are inserted in random order, with all permutations equally
likely. We show a lower bound of 1:08 : : : and an upper
bound of 1:5 on the random order performance ratio of
Best-fit. The upper bound contrasts with the result that in
the worst case, any (deterministic or randomized) on-line
bin-packing algorithm has performance ratio at least
1:54 : : :. 1
3. Un otro paper donde particionan los $x_i$ en tres classes,
placeando los x_i mas grande primero, buscando el
placamiento optimal de los $x_i$ promedio, y usando un
algoritmo greedy para los $x_i$ pequenos. [Karpinski?]
4. la distribucion de los tamaños de las cajas hacen la
instancia dificil o facil.
4 DONE Ejemplo: Recubrimiento de Vertices (Vertex Cover)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-28 Thu 12:00-13:30>
- DEFINICIÓN:
Dado un grafo $G=(V,E)$, cual es el menor $V'\subseteq V$ tal
que $V'$ sea un vertex cover de $G$.
(o sea $V'$ mas pequeño tq $\forall e=(u,v)\in E, u\in V'o v\in V')
- Algoritmo de aproximación:
- V'<- \emptyset
- while E\neq \emptyset
- sea (u,v) \in E
- V'\leftarrow V'\cup {u,v}
- E <- E \ {(x,y), x=u o x=v o y=u o y=v }
- return V
- Discusión: es una 2-aproximación o no?
- LEMA: El algoritmo es una 2-aproximación.
- PRUEBA:
+ Cada par $u,v$ que la aproximación elige esta conectada,
entonces u o v estas en cualquier solucionó óptima de
Vertex Cover.
+ Como se eliminan las aristas incidentes en u y v, los
siguientes pares que se eligen no tienen intersección con
el actual, entonces cada 2 nodos que el algoritmo elige,
uno pertenece a la solución óptima.
+ quod erat demonstrandum, (QED).
5 DONE Ejemplo: Vendedor viajero (Traveling Salesman)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-28 Thu 12:00-13:30>
- DEFINICIÓN:
Dado $G=(V,E)$ dirigido y $C:E\rightarrow R^+$ una función de
costos, encontrar un recorrido que toque cada ciudad una vez, y
minimice la suma de los costos de las aristas recorridas.
- LEMA: Si $c$ satisface la desigualdad triangular
$\forall x,y,z c(x,y)+x(y,z) \geq c(x,z)$,
hay una 2-aproximación.
- PROOF:
- Algoritmo de Aproximación (con desigualdad triangular)
- construir un arbol cobertor mÃ-nimo (MST)
- se puede hacer en tiempo polinomial, con programación lineal.
- C_{MST} \leq C_{OPT}
- producimos un recorrido en profundidad DFS del MST:
- C_{DFS} = 2C_{MST} \leq 2 C_{OPT}
- (factor dos porque el camino de vuelta puede ser al
máximo de tamaño igual al tamaño del camino de ida)
- eliminamos los nodos repetidos del camino, que no crece
el costo
- $C_A\leq 2 C_{OPT}$
- quod erat demonstradndum, QED.
- LEMA: Si $c$ no satisface la desigualdad triangular, el
problema de vendedor viajero no es aproximables en tiempo
polinomial (a menos que P=NP$).
- PROOF:
- Supongamos que existe una p(n)-aproximación de tiempo
polinomial.
- Dado un grafo G=(V,E)
- Construimos un grafo G'=(V,E') tal que
- E'=V^2 (grafo completo), y
- c(u,v) = 1 si (u,v)\in E
n p(n) sino
- Si no hay un Ciclo Hamiltonian en E,
- todas las soluciones usan al menos una arista que no es
en E
- entonces todas las soluciones tienen costo mas que
$np(n)$
- Si hay un Ciclo Hamiltonian en E
- tenemos una aproximación de una solucionó de costo menos
que $(n-1)p(n)$ QED
6 DONE Ejemplo: Vertex Cover con pesos
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-02 Tue 12:00-13:30>
- DEFINICIÓN
Dado G=(V,E) y c:V->R^+, se quiere un V^*\subseteq V que cubra
E y que minimice \sum_{v\in V^*} c(v).
- Este problema es NP Completo.
- LEMA: Vertex Cover con pesos es 2-aproximable
- PROOF:
1. Sea variables x(v)\in {0,1}, \forall v\in V
- el costo de V^* sera \sum x(v) c(v)
- objetivo: \min \sum_{v\in V} x(v) c(v)
donde 0\leq x(v) \leq 1 \forall v\in V
- x(u)+x(v)\geq 1 \forall u,v \in E
2. x(v) \in Z seré programación entera, que es NP Completa
x(v) \in R seré programación lineal, que es polinomial
el valor \sum x(v) c(v) que produce el programo lineal
es inferior a la mejor solución al problema de VC.
3. Algoritmo
- resolver el problema de programación lineal
- nos da x(v_1),\ldots x(v_n)
- V^* <Â \emptyset
- for v\in V
- si x(v)\geq 1/2
- V^* <- V^* \cup {v}
- return V^*
4. Propiedades
- V^* es un vertex cover:
- si \forall(u,v)\in E, x(u)+x(v)\geq 1
- entonces, x(u)\geq 1/2 o x(v)/geq 1/2
- entonces, u\in V^* o v\in V^*
- V^* es una 2-aproximación:
- c(V^*) = \sum_v y(v) c(v)
donde y(v) = 1 si x(v) \geq 1/2
0 sino
- entonces y(v) \leq 2 x(v)
- \sum y(v) c(v) \leq \sum 2 x(v) c(v) \leq 2 OPT
- C(V^*) \leq 2 OPT
5. QED
7 DONE PTAS y FPTAS: Definiciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-04 Thu 12:00-13:30>
* Esquema de aproximacion poliniomial *PTAS*
Un *esquema de aproximación polinomial* para un problema es un
algoritmo $A$ que recibe como input una instancia del problema
y un para-metro $\varepsilon>0$ y produce una $(1+\varepsilon)$
aproximación. Para todo $\varepsilon$ fijo, el tiempo de $A$
debe ser polinomial en $n$, el tamaño de la instancia.
* Ejemplos de complejidades: Cuales tienen sentidos?
- [ ] $O(n^{2/3})$
- [ ] $O(\frac{1}{\varepsilon^2} n^2)$
- [ ] $O(2^\varepsilon n)$
- [ ] $O(2^{1/\varepsilon} n)$
* Esquema de aproximación completamente polinomial *FPTAS*
Un *esquema de aproximación completamente polinomial* es un
PTAS donde el tiempo del algoritmo es polinomial en $n$ *y en
$1/\varepsilon$*.
8 DONE Ejemplo: Problema de la mochila
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-04 Thu 12:00-13:30>
* Definición:
Dado
- los elementos $S={1,\ldots,n}$ con pesos $X_1,\ldots,X_N\geq 0$,
- un tamaño máximo $t$
Quiero encontrar $S'\subset S$
- tal que $\sum(S')\leq t y$
- que maximice $\sum(S')=\sum_{i\in S'} x_i$
* Solucion exacta, exponencial
- Dado $L=\{y_1,,\ldots y_m\}$, definimos $L+x=\{y_1+x,\ldots,y_m+x\}$
- Algoritmo:
- $L \leftarrow \{\emptyset\}$
- for $i\leftarrow 1$ to $n$
- $L \leftarrow$ merge $(L,L+x_i)$
- prune$(L,t)$ (remudando las valores $> t$)
- return $\max(L)$
* Solucion aproximada (inspirada del algoritmo exacto)
- Definimos la operación de *recorte* de una lista L con
parámetro $\delta$:
- Dado $y,z \in L$, $z$ *represente* a $y$ si
- $y /(1+\delta) \leq z \leq y$
- vamos a eliminar de $L$ todos los $y$ que sean representados
por alguno $z$ no eliminado de $L$.
- Recortar$(L,\delta)$
- Sea $L=\{y_1,\ldots,y_m\}$
- $L'\leftarrow \{y_1\}$
- $\mathit{Last} \leftarrow y_1$
- for $i\leftarrow 2$ to $m$
- si $y_i > \mathit{Last}(1+\delta)$
- $L \leftarrow L'.\{y_i\}$
- $\mathit{Last}\leftarrow y_i$
- return $L'$
- Algoritmo de Aproximación:
- $L \leftarrow \{\emptyset\}$
- for $i\leftarrow 1$ to $n$
- $L \leftarrow \mathit{merge} (L,L+x_i)$
- $\mathit{prune}(L,t)$ (remudando las valores $> t$)
- *$L \leftarrow \mathit{recortar}(L,\epsilon/2n)$*
- return max(L)
- El resultado es una $(1+\epsilon)$-aproximación:
1. retorne una solución valida, tal que
- $\sum(S')\leq t$ para algún $S'\subset S$
2. en el paso $i$, para todo $z\in L_{OPT}$,
existe un $y\in L_A$ tal que $z$ representa a $y$.
- Luego de los $n$ pasos, el $z^*$ óptimo en $L_{OPT}$
tiene un representante $y^*\in L_A$ tal que
$z^*/(1+\epsilon/2n)^n \leq y^* \leq z^*
3. Para mostrar que el algoritmo es una $(1+\epsilon)$
aproximación,
- hay que mostrar que
- $z^*/(1+\epsilon) \leq y^*$
- entonces, debemos mostrar que
- $(1+\epsilon/2n)^n \leq 1+\epsilon$
- Eso se muestra con puro calculo:
- $(1+\epsilon/2n)^n \leq? 1+\epsilon$
- $e^{n\lg(1+\epsilon/2n) }$
- $\leq e^{ n \epsilon /2n }$
- $= e^{ \epsilon/2 }$
- $\leq? e^{\ln(1+\epsilon)}$
- eso es equivalente a elegir \epsilon tal
que $\epsilon/2 \leq \ln(1+\epsilon)$
- i.e. cualquier tal que $0<\epsilon\leq 1$
4. El algoritmo es polinomial (en todos los parámetros)
- despues de recortar dedos $y_i,y_{i+1}\in L$
se cumple $y_{i+1}>y_i(1+\delta)$
y el ultimo elemento es $\leq t$
- entonces, la lista contiene $0,1$
y luego a lo mas $\lfloor \log_{(1+\delta)} t \rfloor$
- entonces el largo de L en cada iteracion no supera
$2+ \frac{ \log t }{ \log( 1+\varepsilon/2n) }$
- Nota que $\ln(1+x) $
- $= - \ln (1/(1+x))$
- $= - \ln ( (1+x-x)/(1+x) )$
- $= - \ln ( 1 - x/(1+x) )$
- $= - \ln (1+y) \geq -y$
- $\geq - (-x/(1+x)) = x/(1+x)$
- Entonces
- $2+ \frac{ \ln t }{ \ln 1 + \epsilon/2n }$
- $\leq 2 + ((1+\epsilon/2n) 2n \ln t )/\epsilon$
- $= ( 2n\ln t )/ \epsilon + \ln t + 2$
- $= O(n \lg t /\epsilon)$
- Entonces cada iteracion toma $O(n \lg t /\epsilon)$ operaciones
- Las $n$ iteraciones en total toman
- $O(n^2 \lg t /\epsilon)$ operaciones
===================================================
Author: Jérémy Barbay
[2010-10-26 Tue]--[2010-11-04 Thu]
- problemas que son o no aproximables
Table of Contents
=================
1 Intro: Aproximación de problemas de optimización NP-dificiles
2 *$p(n)$-aproximación*: Definición
3 Ejemplo: Bin Packing (un problema que es 2-aproximable)
4 Ejemplo: Recubrimiento de Vertices (Vertex Cover)
5 Ejemplo: Vendedor viajero (Traveling Salesman)
6 Ejemplo: Vertex Cover con pesos
7 PTAS y FPTAS: Definiciones
8 Ejemplo: Problema de la mochila
1 DONE Intro: Aproximación de problemas de optimización NP-dificiles
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
- Que problemas NP dificiles conocen?
- colorisacion de grafos
- ciclo hamiltonian
- Recubrimiento de Vertices (Vertex Cover)
- Bin Packing
- Problema de la Muchila
- Vendedor viajero (Traveling Salesman)
- Que hacer cuando se necessita una solucion en tiempo
polinomial?
- Consideramos los problemas NP completos de decisión,
generalmente de optimización. Si se necesita una solucionó
en tiempo polinomial, se puede considerar una aproximación.
2 DONE *$p(n)$-aproximación*: Definición
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
* Dado un problema de minimización, un algoritmo $A$ es un
*$p(n)$-aproximación* si
$\forall n \max \frac{ C_A(x) }{ C_{OPT}(x) } \leq p(n)$
* Dado un problema de maximización, un algoritmo $A$ es un
*$p(n)$-aproximación* si
$\forall n \max \frac{ C_{OPT}(x) }{ C_A(x) } \leq p(n)$
- Notas:
1) AquÃ- consideramos la cualidad de la solución, NO la
complejidad del algoritmo. Usualmente el problema es
NP-difÃ-cil, y el algoritmo de aproximación es de
complejidad polinomial.
2) Las razones estas \geq 1 (elijamos las definiciones para
eso)
3) A veces consideramos también C_A(x)-C_{OPT}(x)
(minimización) y C_{OPT}(x)-C_A(x): eso se llama un
"esquema de aproximación polinomial" y vamos a verlo mas
tarde.
3 DONE Ejemplo: Bin Packing (un problema que es 2-aproximable)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
- DEFINICIÓN
Dado $n$ valores $x_1, \ldots, x_n$, $0\leq x_i\leq 1/2$,
cual es la menor cantidad de cajas de tamaño 1 necesarias
para empaquetarlas?
- Algoritmo "Greedy"
- Considerando los $x_i$ en orden,
- llenar la caja actual todo lo posible,
- pasar ala siguiente caja.
- Análisis
- Este algoritmo tiene complejidad lineal O(n).
- Greedy da una 2-aproximación.
- (se puede mostrar facilamente en las instancias donde el
algoritmo óptima llene completamente todas las cajas.)
- Además, hay mejores aproximaciones,
1. Best-fit tiene performance ratio de 1.7 en el peor caso
2. [Best-Fit Bin-Packing with Random Order (1997), Kenyon]
Best-fit is the best known algorithm for on-line
binpacking, in the sense that no algorithm is known to
behave better both in the worst case (when Best-fit has
performance ratio 1.7) and in the average uniform case,
with items drawn uniformly in the interval [0; 1] (then
Best-fit has expected wasted space O(n 1=2 (log n) 3=4
)). In practical applications, Best-fit appears to perform
within a few percent of optimal. In this paper, in the
spirit of previous work in computational geometry, we study
the expected performance ratio, taking the worst-case
multiset of items L, and assuming that the elements of L
are inserted in random order, with all permutations equally
likely. We show a lower bound of 1:08 : : : and an upper
bound of 1:5 on the random order performance ratio of
Best-fit. The upper bound contrasts with the result that in
the worst case, any (deterministic or randomized) on-line
bin-packing algorithm has performance ratio at least
1:54 : : :. 1
3. Un otro paper donde particionan los $x_i$ en tres classes,
placeando los x_i mas grande primero, buscando el
placamiento optimal de los $x_i$ promedio, y usando un
algoritmo greedy para los $x_i$ pequenos. [Karpinski?]
4. la distribucion de los tamaños de las cajas hacen la
instancia dificil o facil.
4 DONE Ejemplo: Recubrimiento de Vertices (Vertex Cover)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-28 Thu 12:00-13:30>
- DEFINICIÓN:
Dado un grafo $G=(V,E)$, cual es el menor $V'\subseteq V$ tal
que $V'$ sea un vertex cover de $G$.
(o sea $V'$ mas pequeño tq $\forall e=(u,v)\in E, u\in V'o v\in V')
- Algoritmo de aproximación:
- V'<- \emptyset
- while E\neq \emptyset
- sea (u,v) \in E
- V'\leftarrow V'\cup {u,v}
- E <- E \ {(x,y), x=u o x=v o y=u o y=v }
- return V
- Discusión: es una 2-aproximación o no?
- LEMA: El algoritmo es una 2-aproximación.
- PRUEBA:
+ Cada par $u,v$ que la aproximación elige esta conectada,
entonces u o v estas en cualquier solucionó óptima de
Vertex Cover.
+ Como se eliminan las aristas incidentes en u y v, los
siguientes pares que se eligen no tienen intersección con
el actual, entonces cada 2 nodos que el algoritmo elige,
uno pertenece a la solución óptima.
+ quod erat demonstrandum, (QED).
5 DONE Ejemplo: Vendedor viajero (Traveling Salesman)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-28 Thu 12:00-13:30>
- DEFINICIÓN:
Dado $G=(V,E)$ dirigido y $C:E\rightarrow R^+$ una función de
costos, encontrar un recorrido que toque cada ciudad una vez, y
minimice la suma de los costos de las aristas recorridas.
- LEMA: Si $c$ satisface la desigualdad triangular
$\forall x,y,z c(x,y)+x(y,z) \geq c(x,z)$,
hay una 2-aproximación.
- PROOF:
- Algoritmo de Aproximación (con desigualdad triangular)
- construir un arbol cobertor mÃ-nimo (MST)
- se puede hacer en tiempo polinomial, con programación lineal.
- C_{MST} \leq C_{OPT}
- producimos un recorrido en profundidad DFS del MST:
- C_{DFS} = 2C_{MST} \leq 2 C_{OPT}
- (factor dos porque el camino de vuelta puede ser al
máximo de tamaño igual al tamaño del camino de ida)
- eliminamos los nodos repetidos del camino, que no crece
el costo
- $C_A\leq 2 C_{OPT}$
- quod erat demonstradndum, QED.
- LEMA: Si $c$ no satisface la desigualdad triangular, el
problema de vendedor viajero no es aproximables en tiempo
polinomial (a menos que P=NP$).
- PROOF:
- Supongamos que existe una p(n)-aproximación de tiempo
polinomial.
- Dado un grafo G=(V,E)
- Construimos un grafo G'=(V,E') tal que
- E'=V^2 (grafo completo), y
- c(u,v) = 1 si (u,v)\in E
n p(n) sino
- Si no hay un Ciclo Hamiltonian en E,
- todas las soluciones usan al menos una arista que no es
en E
- entonces todas las soluciones tienen costo mas que
$np(n)$
- Si hay un Ciclo Hamiltonian en E
- tenemos una aproximación de una solucionó de costo menos
que $(n-1)p(n)$ QED
6 DONE Ejemplo: Vertex Cover con pesos
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-02 Tue 12:00-13:30>
- DEFINICIÓN
Dado G=(V,E) y c:V->R^+, se quiere un V^*\subseteq V que cubra
E y que minimice \sum_{v\in V^*} c(v).
- Este problema es NP Completo.
- LEMA: Vertex Cover con pesos es 2-aproximable
- PROOF:
1. Sea variables x(v)\in {0,1}, \forall v\in V
- el costo de V^* sera \sum x(v) c(v)
- objetivo: \min \sum_{v\in V} x(v) c(v)
donde 0\leq x(v) \leq 1 \forall v\in V
- x(u)+x(v)\geq 1 \forall u,v \in E
2. x(v) \in Z seré programación entera, que es NP Completa
x(v) \in R seré programación lineal, que es polinomial
el valor \sum x(v) c(v) que produce el programo lineal
es inferior a la mejor solución al problema de VC.
3. Algoritmo
- resolver el problema de programación lineal
- nos da x(v_1),\ldots x(v_n)
- V^* <Â \emptyset
- for v\in V
- si x(v)\geq 1/2
- V^* <- V^* \cup {v}
- return V^*
4. Propiedades
- V^* es un vertex cover:
- si \forall(u,v)\in E, x(u)+x(v)\geq 1
- entonces, x(u)\geq 1/2 o x(v)/geq 1/2
- entonces, u\in V^* o v\in V^*
- V^* es una 2-aproximación:
- c(V^*) = \sum_v y(v) c(v)
donde y(v) = 1 si x(v) \geq 1/2
0 sino
- entonces y(v) \leq 2 x(v)
- \sum y(v) c(v) \leq \sum 2 x(v) c(v) \leq 2 OPT
- C(V^*) \leq 2 OPT
5. QED
7 DONE PTAS y FPTAS: Definiciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-04 Thu 12:00-13:30>
* Esquema de aproximacion poliniomial *PTAS*
Un *esquema de aproximación polinomial* para un problema es un
algoritmo $A$ que recibe como input una instancia del problema
y un para-metro $\varepsilon>0$ y produce una $(1+\varepsilon)$
aproximación. Para todo $\varepsilon$ fijo, el tiempo de $A$
debe ser polinomial en $n$, el tamaño de la instancia.
* Ejemplos de complejidades: Cuales tienen sentidos?
- [ ] $O(n^{2/3})$
- [ ] $O(\frac{1}{\varepsilon^2} n^2)$
- [ ] $O(2^\varepsilon n)$
- [ ] $O(2^{1/\varepsilon} n)$
* Esquema de aproximación completamente polinomial *FPTAS*
Un *esquema de aproximación completamente polinomial* es un
PTAS donde el tiempo del algoritmo es polinomial en $n$ *y en
$1/\varepsilon$*.
8 DONE Ejemplo: Problema de la mochila
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-04 Thu 12:00-13:30>
* Definición:
Dado
- los elementos $S={1,\ldots,n}$ con pesos $X_1,\ldots,X_N\geq 0$,
- un tamaño máximo $t$
Quiero encontrar $S'\subset S$
- tal que $\sum(S')\leq t y$
- que maximice $\sum(S')=\sum_{i\in S'} x_i$
* Solucion exacta, exponencial
- Dado $L=\{y_1,,\ldots y_m\}$, definimos $L+x=\{y_1+x,\ldots,y_m+x\}$
- Algoritmo:
- $L \leftarrow \{\emptyset\}$
- for $i\leftarrow 1$ to $n$
- $L \leftarrow$ merge $(L,L+x_i)$
- prune$(L,t)$ (remudando las valores $> t$)
- return $\max(L)$
* Solucion aproximada (inspirada del algoritmo exacto)
- Definimos la operación de *recorte* de una lista L con
parámetro $\delta$:
- Dado $y,z \in L$, $z$ *represente* a $y$ si
- $y /(1+\delta) \leq z \leq y$
- vamos a eliminar de $L$ todos los $y$ que sean representados
por alguno $z$ no eliminado de $L$.
- Recortar$(L,\delta)$
- Sea $L=\{y_1,\ldots,y_m\}$
- $L'\leftarrow \{y_1\}$
- $\mathit{Last} \leftarrow y_1$
- for $i\leftarrow 2$ to $m$
- si $y_i > \mathit{Last}(1+\delta)$
- $L \leftarrow L'.\{y_i\}$
- $\mathit{Last}\leftarrow y_i$
- return $L'$
- Algoritmo de Aproximación:
- $L \leftarrow \{\emptyset\}$
- for $i\leftarrow 1$ to $n$
- $L \leftarrow \mathit{merge} (L,L+x_i)$
- $\mathit{prune}(L,t)$ (remudando las valores $> t$)
- *$L \leftarrow \mathit{recortar}(L,\epsilon/2n)$*
- return max(L)
- El resultado es una $(1+\epsilon)$-aproximación:
1. retorne una solución valida, tal que
- $\sum(S')\leq t$ para algún $S'\subset S$
2. en el paso $i$, para todo $z\in L_{OPT}$,
existe un $y\in L_A$ tal que $z$ representa a $y$.
- Luego de los $n$ pasos, el $z^*$ óptimo en $L_{OPT}$
tiene un representante $y^*\in L_A$ tal que
$z^*/(1+\epsilon/2n)^n \leq y^* \leq z^*
3. Para mostrar que el algoritmo es una $(1+\epsilon)$
aproximación,
- hay que mostrar que
- $z^*/(1+\epsilon) \leq y^*$
- entonces, debemos mostrar que
- $(1+\epsilon/2n)^n \leq 1+\epsilon$
- Eso se muestra con puro calculo:
- $(1+\epsilon/2n)^n \leq? 1+\epsilon$
- $e^{n\lg(1+\epsilon/2n) }$
- $\leq e^{ n \epsilon /2n }$
- $= e^{ \epsilon/2 }$
- $\leq? e^{\ln(1+\epsilon)}$
- eso es equivalente a elegir \epsilon tal
que $\epsilon/2 \leq \ln(1+\epsilon)$
- i.e. cualquier tal que $0<\epsilon\leq 1$
4. El algoritmo es polinomial (en todos los parámetros)
- despues de recortar dedos $y_i,y_{i+1}\in L$
se cumple $y_{i+1}>y_i(1+\delta)$
y el ultimo elemento es $\leq t$
- entonces, la lista contiene $0,1$
y luego a lo mas $\lfloor \log_{(1+\delta)} t \rfloor$
- entonces el largo de L en cada iteracion no supera
$2+ \frac{ \log t }{ \log( 1+\varepsilon/2n) }$
- Nota que $\ln(1+x) $
- $= - \ln (1/(1+x))$
- $= - \ln ( (1+x-x)/(1+x) )$
- $= - \ln ( 1 - x/(1+x) )$
- $= - \ln (1+y) \geq -y$
- $\geq - (-x/(1+x)) = x/(1+x)$
- Entonces
- $2+ \frac{ \ln t }{ \ln 1 + \epsilon/2n }$
- $\leq 2 + ((1+\epsilon/2n) 2n \ln t )/\epsilon$
- $= ( 2n\ln t )/ \epsilon + \ln t + 2$
- $= O(n \lg t /\epsilon)$
- Entonces cada iteracion toma $O(n \lg t /\epsilon)$ operaciones
- Las $n$ iteraciones en total toman
- $O(n^2 \lg t /\epsilon)$ operaciones
| Last Edit | 9 Nov 201009/11/10 at 11:322010-11-09 11:32:09 |
|---|---|
| Unique Views | 4 |
| Compartir |
