Hispanopedia Wiki
Articulo de referencia

Esquema de aproximación totalmente polinomial

Un esquema de aproximación de tiempo totalmente polinomial (FPTAS) es un algoritmo para encontrar soluciones aproximadas a problemas de funciones , especialmente problemas de op...

Hispanopedia WikiContenido en espanolLectura gratuita

Un esquema de aproximación de tiempo totalmente polinomial (FPTAS) es un algoritmo para encontrar soluciones aproximadas a problemas de funciones , especialmente problemas de optimización . Un FPTAS toma como entrada una instancia del problema y un parámetro ε  >  0. Devuelve como salida un valor que es al menos1−ε{\displaystyle 1-\varepsilon }veces el valor correcto, y como máximo1+ε{\displaystyle 1+\varepsilon }veces el valor correcto.

En el contexto de los problemas de optimización, se entiende que el valor correcto es el valor de la solución óptima, y ​​a menudo se da por sentado que un FPTAS debería producir una solución válida (y no solo el valor de la solución). Devolver un valor y encontrar una solución con ese valor son equivalentes, suponiendo que el problema posee autorreductibilidad .

Es importante destacar que el tiempo de ejecución de un FPTAS es polinómico en el tamaño del problema y en 1/ε. Esto contrasta con un esquema de aproximación de tiempo polinómico general (PTAS). El tiempo de ejecución de un PTAS general es polinómico en el tamaño del problema para cada ε específico, pero podría ser exponencial en 1/ε. [ 1 ]

El término FPTAS también puede usarse para referirse a la clase de problemas que tienen un FPTAS. FPTAS es un subconjunto de PTAS y, a menos que P = NP , es un subconjunto estricto. [ 2 ]

Relación con otras clases de complejidad

Todos los problemas en FPTAS son tratables con parámetros fijos respecto a la parametrización estándar. [ 3 ]

Cualquier problema de optimización fuertemente NP-difícil con una función objetivo acotada polinómicamente no puede tener un FPTAS a menos que P=NP. [ 4 ] Sin embargo, lo contrario no se cumple: por ejemplo, si P no es igual a NP, el problema de la mochila con dos restricciones no es fuertemente NP-difícil, pero no tiene FPTAS incluso cuando la función objetivo óptima está acotada polinómicamente. [ 5 ]

Conversión de un programa dinámico a un FPTAS

Woeginger [ 6 ] presentó un esquema general para convertir una determinada clase de programas dinámicos a un FPTAS.

Aporte

El esquema maneja problemas de optimización en los que la entrada se define de la siguiente manera:

  • La entrada está compuesta por n vectores, x 1 ,..., x n .
  • Cada vector de entrada está compuesto por algunosa{\displaystyle a}enteros no negativos, dondea{\displaystyle a}puede depender de la entrada.
  • Todos los componentes de los vectores de entrada están codificados en binario. Por lo tanto, el tamaño del problema es O( n +log( X )), donde X es la suma de todos los componentes en todos los vectores.

Programa dinámico extremadamente sencillo

Se supone que el problema tiene un algoritmo de programación dinámica (PD) que utiliza estados . Cada estado es un vector formado por algunosb{\displaystyle b}enteros no negativos, dondeb{\displaystyle b}es independiente de la entrada. El DP funciona en n pasos. En cada paso i , procesa la entrada x i y construye un conjunto de estados S i . Cada estado codifica una solución parcial al problema, utilizando las entradas x 1 ,..., x i . Los componentes del DP son:

  • Un conjunto S 0 de estados iniciales .
  • Un conjunto F de funciones de transición. Cada función f en F asigna un par (estado, entrada) a un nuevo estado.
  • Una función objetivo g, que asigna un estado a su valor.

El algoritmo de la programación dinámica es:

  • Sea S 0  := el conjunto de estados iniciales.
  • Para k = 1 a n , haga lo siguiente:
    • Sea S k  := { f ( s , x k ) | f en F , s en S k −1 }
  • Salida min/max {g(s) | s en S n }.

El tiempo de ejecución del DP es lineal en el número de estados posibles. En general, este número puede ser exponencial en el tamaño del problema de entrada: puede ser de O( n V b ), donde V es el entero más grande que puede aparecer en un estado. Si V es de O( X ), entonces el tiempo de ejecución es de O( n X b ), que es solo un tiempo pseudopolinomial , ya que es exponencial en el tamaño del problema que es de O(log X ).

La forma de lograr que sea polinomial es recortar el espacio de estados : en lugar de conservar todos los estados posibles en cada paso, se conserva solo un subconjunto; se eliminan los estados que están "suficientemente cerca" de otros. Bajo ciertas condiciones, este recorte se puede realizar de manera que el valor de la función objetivo no se vea afectado significativamente.

Para formalizar esto, asumimos que el problema en cuestión tiene un vector entero no negativo d = ( d 1 ,..., d b ), llamado vector de grado del problema. Para cada número real r >1, decimos que dos vectores de estado s 1 , s 2 son (d,r)-cercanos si, para cada coordenada j en 1,..., b : r−dj⋅s1,j≤s2,j≤rdj⋅s1,j{\displaystyle r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}}(en particular, si d j =0 para algún j , entoncess1,j=s2,j{\displaystyle s_{1,j}=s_{2,j}}).

Un problema se denomina extremadamente benevolente si cumple las tres condiciones siguientes:

  1. La proximidad se conserva mediante las funciones de transición : Para cualquier r >1, para cualquier función de transición f en F , para cualquier vector de entrada x , y para cualesquiera dos vectores de estado s 1 , s 2 , se cumple lo siguiente: si s 1 está ( d,r )-cerca de s 2 , entonces f ( s 1 , x ) está ( d,r )-cerca de f ( s 2 ,x ).
    • Una condición suficiente para esto se puede comprobar de la siguiente manera. Para cada función f ( s , x ) en F , y para cada coordenada j en 1,..., b , denotemos por f j (s,x) la j -ésima coordenada de f . Esta f j puede verse como una función entera en b + a variables. Supongamos que cada f j es un polinomio con coeficientes no negativos. Convirtámoslo en un polinomio de una sola variable z , sustituyendo s =(z d1 ,...,z db ) y x =(1,...,1). Si el grado del polinomio resultante en z es como máximo d j , entonces se cumple la condición 1.
  2. La proximidad se conserva mediante la función de valor : Existe un entero G ≥ 0 (que es una función de la función de valor g y el vector de grado d ), tal que para cualquier r > 1, y para cualesquiera dos vectores de estado s 1 , s 2 , se cumple lo siguiente: si s 1 está ( d,r )-cercano a s 2 , entonces: g ( s 1 ) ≤ r G · g ( s 2 ) (en problemas de minimización); g ( s 1 ) ≥ r (-G) · g ( s 2 ) (en problemas de maximización).
    • Una condición suficiente para ello es que la función g sea una función polinómica (de b variables) con coeficientes no negativos.
  3. Condiciones técnicas :
    • Todas las funciones de transición f en F y la función de valor g pueden evaluarse en tiempo polinomial.
    • El número | F | de funciones de transición es polinómico en n y log( X ).
    • El conjunto S 0 de estados iniciales se puede calcular en tiempo polinomial en n y log( X ).
    • Sea V j el conjunto de todos los valores que pueden aparecer en la coordenada j en un estado. Entonces, el ln de cada valor en V j es como máximo un polinomio P 1 (n,log(X)).
    • Si d j =0, la cardinalidad de V j es como máximo un polinomio P 2 ( n ,log( X )).

Para cada problema extremadamente benevolente, el programa dinámico se puede convertir en un FPTAS. Definir:

  • ϵ{\displaystyle \epsilon } := la relación de aproximación requerida.
  • r:=1+ϵ2GRAMOnorte{\displaystyle r:=1+{\frac {\epsilon }{2Gn}}}, donde G es la constante de la condición 2. Nótese que1ln⁡r≤1+2GRAMOnorteϵ{\displaystyle {\frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}}.
  • L:=⌈PAG1(norte,registro⁡(incógnita))ln⁡(r)⌉{\displaystyle L:=\left\lceil {\frac {P_{1}(n,\log(X))}{\ln(r)}}\right\rceil }, donde P 1 es el polinomio de la condición 3 (una cota superior para el ln de cada valor que puede aparecer en un vector de estado). Nótese queL≤⌈(1+2GRAMOnorteϵ)PAG1(norte,registro⁡incógnita)⌉{\displaystyle L\leq \left\lceil \left(1+{\frac {2Gn}{\epsilon }}\right)P_{1}(n,\log {X})\right\rceil }, por lo que es polinomial en el tamaño de la entrada y en1/ϵ{\displaystyle 1/\epsilon }. También,rL=miln⁡r⋅L≥miPAG1(norte,registro⁡incógnita){\displaystyle r^{L}=e^{\ln {r}}\cdot L\geq e^{P_{1}(n,\log {x})}}, por definición de P 1 , cada entero que puede aparecer en un vector de estado está en el rango [0, r L ].
  • Dividir el rango [0, r L ] en L +1 intervalos de r :I0=[0];I1=[1,r);I2=[r,r2);…;IL=[rL−1,rL]{\displaystyle I_{0}=[0];I_{1}=[1,r);I_{2}=[r,r^{2});\ldots ;I_{L}=[r^{L-1},r^{L}]}.
  • Dividir el espacio de estados en r-cajas : cada coordenada k con grado d k ≥ 1 se divide en los L +1 intervalos anteriores; cada coordenada con d k = 0 se divide en P 2 ( n ,log( X )) intervalos unitarios, un intervalo para cada posible valor de la coordenada k (donde P 2 es el polinomio de la condición 3 anterior).
    • Tenga en cuenta que cada estado posible está contenido en exactamente una r -caja; si dos estados están en la misma r -caja, entonces están ( d , r )-cercanos.
  • R:=(L+1+PAG2(norte,registro⁡incógnita))b{\displaystyle R:=(L+1+P_{2}(n,\log {X}))^{b}}.
    • Nótese que el número de r -cajas es como máximo R. Dado que b es una constante fija, este R es polinomial en el tamaño de la entrada y en1/ϵ{\displaystyle 1/\epsilon }.

El FPTAS funciona de forma similar al DP, pero en cada paso, reduce el conjunto de estados a un conjunto más pequeño T k , que contiene exactamente un estado en cada r -caja. El algoritmo del FPTAS es:

  • Sea T 0  := S 0 = el conjunto de estados iniciales.
  • Para k = 1 a n , haga lo siguiente:
    • Sea U k  := { f ( s , x k ) | f en F , s en T k −1 }
    • Sea T k  := una copia recortada de U k : para cada r -caja que contiene uno o más estados de U k , mantenga exactamente un estado en T k .
  • Salida min/max {g(s) | s en T n }.

El tiempo de ejecución del FPTAS es polinomial en el número total de estados posibles en cada T i , que es como máximo el número total de r -cajas, que es como máximo R , que es polinomial en n , log( X ), y1/ϵ{\displaystyle 1/\epsilon }.

Nótese que, para cada estado s u en U k , su subconjunto T k contiene al menos un estado s t que es (d,r)-cercano a s u . Además, cada U k es un subconjunto de S k en el DP original (sin recortar). El lema principal para probar la corrección del FPTAS es: [ 6 ] : Lem.3.3

Para cada paso k en 0,..., n , para cada estado s s en S k , hay un estado s t en T k que está ( d , r k )-cercano a s s .

La demostración es por inducción sobre k . Para k = 0 tenemos T k = S k ; cada estado es ( d ,1)-cercano a sí mismo. Supongamos que el lema se cumple para k -1. Para cada estado s s en S k , sea s s- uno de sus predecesores en S k-1 , de modo que f ( s s − , x )= s s . Por la suposición de inducción, hay un estado s t- en T k-1 , que es ( d , r k-1 )-cercano a s s − . Dado que la proximidad se conserva por transiciones (Condición 1 anterior), f ( s t − , x ) es ( d , r k-1 )-cercano a f ( s s − , x )= s s . Este f ( s t − , x ) está en U k . Después del recorte, hay un estado s t en T k que está ( d , r )-cercano a f(s t- ,x) . Este s t está ( d , r k )-cercano a s s .

Consideremos ahora el estado s * en S n , que corresponde a la solución óptima (es decir, g ( s* )=OPT). Por el lema anterior, hay un estado t * en T n , que está ( d , r n )-cercano a s * . Dado que la proximidad se conserva mediante la función de valor, g (t*) ≥ r (-Gn) · g ( s* ) para un problema de maximización. Por definición de r ,r−GRAMOnorte≥(1−ϵ){\displaystyle r^{-Gn}\geq (1-\epsilon )}. Entoncesgramo(t∗)≥(1−ϵ)⋅OPAGT{\displaystyle g(t^{*})\geq (1-\epsilon )\cdot OPT}Un argumento similar funciona para un problema de minimización.

Ejemplos

Aquí hay algunos ejemplos de problemas extremadamente benevolentes, que tienen un FPTAS según el teorema anterior. [ 6 ]

1. La partición de números multivariados (equivalentemente, programación de máquinas idénticas ) con el objetivo de minimizar la suma más grande es extremadamente benevolente. Aquí, tenemos a = 1 (las entradas son enteros) y b = el número de contenedores (que se considera fijo). Cada estado es un vector de b enteros que representan las sumas de los b contenedores. Hay b funciones: cada función j representa la inserción de la siguiente entrada en el contenedor j . La función g ( s ) elige el elemento más grande de s . S0 = {( 0 ,...,0)}. Las condiciones para la extrema benevolencia se satisfacen con el vector de grado d = (1,...,1) y G = 1. El resultado se extiende a la programación de máquinas uniformes y a la programación de máquinas no relacionadas siempre que el número de máquinas sea fijo (esto es necesario porque R , el número de r -cajas, es exponencial en b ). Denotado Pm||máximodoj{\displaystyle \max C_{j}}o Qm||máximodoj{\displaystyle \max C_{j}}o Rm||máximodoj{\displaystyle \max C_{j}}.

  • Nota : considérese el caso especial b = 2, donde el objetivo es minimizar el cuadrado de la diferencia entre las sumas de las dos partes. Se puede usar el mismo DP, pero esta vez con la función de valor g ( s ) = ( s 1 - s 2 ) 2 . Ahora, se viola la condición 2: los estados ( s 1 , s 1 ) y ( s 1 , s 2 ) pueden ser ( d,r )-cercanos, pero g ( s 1 , s 1 ) = 0 mientras que g ( s 1 , s 2 ) > 0. por lo que el teorema anterior no se puede aplicar. De hecho, el problema no tiene un FPTAS a menos que P=NP, ya que un FPTAS podría usarse para decidir en tiempo polinomial si el valor óptimo es 0.

2. Suma del tiempo de finalización del trabajo al cubo en cualquier número fijo de máquinas idénticas o uniformes, estas últimas denotadas por Qm||∑doj3{\displaystyle \sum C_{j}^{3}}- es ex-benevolente con a =1, b =3, d=(1,1,3). Puede extenderse a cualquier potencia fija del tiempo de finalización.

3. Suma del tiempo de finalización ponderado en cualquier número fijo de máquinas idénticas o uniformes, estas últimas denotadas por Qm||∑wjdoj{\displaystyle \sum w_{j}C_{j}}.

4. Suma del tiempo de finalización en cualquier número fijo de máquinas idénticas o uniformes, con tiempos de procesamiento dependientes del tiempo: Qm|tiempo-dependiente|∑doj{\displaystyle \sum C_{j}}Esto se cumple incluso para la suma ponderada del tiempo de finalización.

5. Adelanto-retraso ponderado alrededor de una fecha de vencimiento común en cualquier número fijo de máquinas: m||∑wj|doj|{\displaystyle \sum w_{j}|C_{j}|}.

Programa dinámico simple

Los programas dinámicos simples añaden a la formulación anterior los siguientes componentes:

  • Un conjunto H de funciones de filtrado , de la misma cardinalidad que F. Cada función h i en H asigna un par (estado, entrada) a un valor booleano. El valor debe ser "verdadero" si y solo si la activación de la transición f i en este par conduce a un estado válido.
  • Una relación de dominancia , que es un orden parcial en los estados (sin indiferencias, no todos los pares son comparables), y una relación de cuasi-dominancia , que es un preorden total en los estados (se permiten indiferencias, todos los pares son comparables).

El DP original se modifica de la siguiente manera:

  • Sea S 0  := el conjunto de estados iniciales.
  • Para k = 1 a n , haga lo siguiente:
    • Sea S k  := { f j ( s , x k ) | f j en F , s en S k −1 , h j ( s , x k )=True }, donde h j es la función de filtro correspondiente a la función de transición f j .
  • Salida min/max {g(s) | s en S n }.

Un problema se denomina benevolente si satisface las siguientes condiciones (que extienden las condiciones 1, 2 y 3 anteriores):

  1. La proximidad se conserva mediante las funciones de transición : Para cualquier r > 1, para cualquier función de transición f en F , para cualquier vector de entrada x y para cualesquiera dos vectores de estado s 1 , s 2 , se cumple lo siguiente:
    • Si s 1 está ( d,r )-cercano a s 2 , y s 1 cuasidomina a s 2 , entonces o bien (a) f ( s 1 , x ) está ( d,r )-cercano a f ( s 2 ,x ), y f ( s 1 , x ) cuasidomina a f ( s 2 ,x ) , o bien (b) f ( s 1 , x ) domina a f ( s 2 ,x ).
    • Si s 1 domina a s 2 , entonces f ( s 1 , x ) domina a f ( s 2 ,x ).
  2. La proximidad se conserva mediante la función de valor: Existe un entero G ≥ 0 (una función de la función de valor g y el vector de grado d ), tal que para cualquier r > 1, y para cualesquiera dos vectores de estado s 1 , s 2 , se cumple lo siguiente:
    • si s 1 es ( d,r )-cercano a s 2 , y s 1 cuasidomina a s 2, entonces: g ( s 1 ) ≤ r G · g ( s 2 ) (en problemas de minimización); g ( s 1 ) ≥ r (-G) · g ( s 2 ) (en problemas de maximización).
    • Si s 1 domina a s 2 , entonces g ( s 1 ) ≤ g ( s 2 ) (en problemas de minimización); g ( s 1 ) ≥ g ( s 2 ) (en problemas de maximización).
  3. Condiciones técnicas (además de las anteriores):
    • La relación de cuasi-dominancia se puede determinar en tiempo polinomial.
  4. Condiciones sobre las funciones de filtro : Para cualquier r > 1, para cualquier función de filtro h en H , para cualquier vector de entrada x , y para cualesquiera dos vectores de estado s 1 , s 2 , se cumple lo siguiente:
    • Si s 1 está ( d,r )-cercano a s 2 , y s 1 cuasidomina a s 2 , entonces h ( s 1 , x ) ≥ h ( s 2 , x ) .
    • Si s 1 domina a s 2 , entonces h ( s 1 , x ) ≥ h ( s 2 , x ).

Para cada problema benevolente, el programa dinámico se puede convertir en un FPTAS de forma similar al anterior, con dos cambios (en negrita):

  • Sea T 0  := S 0 = el conjunto de estados iniciales.
  • Para k = 1 a n , haga lo siguiente:
    • Sea U k  := { f j ( s , x k ) | f j en F , s en T k −1 , h j ( s , x k )=True }, donde h j es la función de filtro correspondiente a la función de transición f j .
    • Sea T k  := una copia recortada de U k : para cada r -caja que contiene uno o más estados de U k , elija un único elemento que cuasi-domine a todos los demás elementos en U k , e insértelo en T k .
  • Salida min/max {g(s) | s en T n }.

Ejemplos

Aquí hay algunos ejemplos de problemas benevolentes que tienen un FPTAS según el teorema anterior. [ 6 ]

1. El problema de la mochila 0-1 es benevolente. Aquí, tenemos a = 2: cada entrada es un vector de 2 elementos (peso, valor). Hay un DP con b = 2: cada estado codifica (peso actual, valor actual). Hay dos funciones de transición: f 1 corresponde a agregar el siguiente elemento de entrada, y f 2 corresponde a no agregarlo. Las funciones de filtro correspondientes son: h 1 verifica que el peso con el siguiente elemento de entrada sea como máximo la capacidad de la mochila; h 2 siempre devuelve Verdadero. La función de valor g ( s ) devuelve s 2 . El conjunto de estados inicial es {(0,0)}. El vector de grado es (1,1). La relación de dominancia es trivial. La relación de cuasi-dominancia compara solo la coordenada de peso: s cuasi-domina a t si y solo si s 1 ≤ t 1 . Esto implica que, si el estado t tiene un peso mayor que el estado s , entonces las funciones de transición pueden no preservar la proximidad entre t y s (es posible, por ejemplo, que s tenga un sucesor y t no tenga un sucesor correspondiente). Un algoritmo similar fue presentado anteriormente por Ibarra y Kim. [ 7 ] El tiempo de ejecución de este FPTAS puede mejorarse aO(norteregistro⁡1/ϵ+1/ϵ4){\displaystyle O(n\log {1/\epsilon }+1/\epsilon ^{4})}operaciones con enteros. [ 8 ] El exponente se mejoró posteriormente a 2,5. [ 9 ]

  • Nota : Consideremos el problema de la mochila con dos pesos , donde cada artículo tiene dos pesos y un valor, y el objetivo es maximizar el valor de tal manera que la suma de los cuadrados de los pesos totales sea como máximo la capacidad de la mochila: (∑k∈Kw1,k)2+(∑k∈Kw2,k)2≤W{\displaystyle \left(\sum _{k\in K}w_{1,k}\right)^{2}+\left(\sum _{k\in K}w_{2,k}\right)^{2}\leq W}Podríamos resolverlo usando un DP similar, donde cada estado es (peso actual 1, peso actual 2, valor). La relación de cuasi-dominancia debería modificarse a: s cuasi-domina a t si y solo si ( s 1 2 + s 2 2 ) ≤ ( t 1 2 + t 2 2 ). Pero viola la Condición 1 anterior: la cuasi-dominancia no se conserva mediante funciones de transición [por ejemplo, el estado (2,2,..) cuasi-domina a (1,3,..); pero después de agregar la entrada (2,0,..) a ambos estados, el resultado (4,2,..) no cuasi-domina a (3,3,..)]. Por lo tanto, el teorema no se puede usar. De hecho, este problema no tiene un FPTAS a menos que P=NP. Lo mismo es cierto para el problema de la mochila bidimensional. Lo mismo ocurre con el problema de la suma de subconjuntos múltiples : la relación de cuasi-dominancia debería ser: s cuasi-domina a t si y solo si max( s 1, s 2 ) ≤ max( t 1, t 2 ), pero no se conserva mediante transiciones, según el mismo ejemplo anterior.

2. Minimizar el número ponderado de trabajos tardíos, o maximizar el número ponderado de trabajos tempranos, en una sola máquina; denotado 1||∑wjUj{\displaystyle \sum w_{j}U_{j}}.

3. Programación por lotes para minimizar el número ponderado de trabajos retrasados: 1|lote|∑wjUj{\displaystyle \sum w_{j}U_{j}}.

4. Duración total de trabajos que se deterioran en una sola máquina: 1|deteriorarse|máximodoj{\displaystyle \max C_{j}}.

5. Total de trabajo atrasado en una sola máquina: 1||∑Vj{\displaystyle \sum V_{j}}.

6. Trabajo total ponderado atrasado en una sola máquina: 1||∑wjVj{\displaystyle \sum w_{j}V_{j}}.

No ejemplos

A pesar de la generalidad del resultado anterior, existen casos en los que no se puede utilizar.

1. En el problema de tardanza total 1||∑Tj{\displaystyle \sum T_{j}}La formulación de programación dinámica de Lawler [ 10 ] requiere actualizar todos los estados en el espacio de estados anterior unas B veces, donde B es del orden de X (el tamaño máximo de entrada). Lo mismo ocurre con un DP para el dimensionamiento económico de lotes. [ 11 ] En estos casos, el número de funciones de transición en F es B , que es exponencial en log( X ), por lo que se incumple la segunda condición técnica. La técnica de recorte de estados no es útil, pero se ha utilizado otra técnica, el redondeo de entradas, para diseñar un FPTAS. [ 12 ] [ 13 ]

2. En el problema de minimización de la varianza 1||doTV{\displaystyle CTV}, la función objetivo es gramo(s)=s5−(s4−s3)2/norte{\displaystyle g(s)=s_{5}-(s_{4}-s_{3})^{2}/n}, lo cual viola la Condición 2, por lo que el teorema no puede utilizarse. Pero se han utilizado diferentes técnicas para diseñar un FPTAS. [ 14 ] [ 15 ]

FPTAS para aproximar números reales

Otro tipo de problema en el que FPTAS puede ser útil es encontrar números racionales que se aproximen a algunos números reales. Por ejemplo, consideremos la serie infinita.∑i=1∞1i3{\displaystyle \sum _{i=1}^{\infty }{\frac {1}{i^{3}}}}La suma es un número irracional . Para aproximarla mediante un número racional, podemos calcular la suma de los primeros k elementos, para algún k finito . Se puede demostrar que el error de aproximación es aproximadamente12k2{\displaystyle {\frac {1}{2k^{2}}}}Por lo tanto, para obtener un error de ε, necesitamos aproximadamente12ϵ{\displaystyle {\sqrt {\frac {1}{2\epsilon }}}}elementos, por lo que se trata de un FPTAS. Nótese que esta suma en particular puede representarse mediante otra suma en la que solo se necesitan O(log(ε)) elementos, por lo que la suma puede aproximarse en tiempo polinomial en la longitud de codificación de ε. [ 16 ] : 35, Sec.1

Otros problemas que tienen un FPTAS

Véase también

  • Los "programas dinámicos benevolentes", que admiten un FPTAS, también admiten un algoritmo evolutivo. [ 30 ]

Referencias

  1. ↑ G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela y M. Protasi. Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximabilidad , Springer-Verlag, 1999.
  2. ↑ Jansen, Thomas (1998), "Introducción a la teoría de la complejidad y los algoritmos de aproximación", en Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms , Lecture Notes in Computer Science, vol.  1367, Springer, pp. 5–28 , doi : 10.1007/BFb0053011 , ISBN  9783540642015. Véase la discusión que sigue a la Definición 1.30 en la página  20 .
  3. ↑ Cai, Liming; Chen, Jianer (junio de 1997). "Sobre la tratabilidad y aproximación de parámetros fijos de problemas de optimización NP" . Journal of Computer and System Sciences . 54 (3): 465– 474. doi : 10.1006/jcss.1997.1490 .
  4. ^ Vazirani, Vijay V. (2003). Algoritmos de aproximación . Berlín: Springer. Corolario 8.6. ISBN 3-540-65367-8.
  5. ↑ H. Kellerer; U. Pferschy; D. Pisinger (2004). Problemas de la mochila . Springer. Teorema 9.4.1.
  6. 1 2 3 4 Woeginger, Gerhard J. (2000-02-01). "¿Cuándo garantiza una formulación de programación dinámica la existencia de un esquema de aproximación de tiempo totalmente polinomial (FPTAS)?" . INFORMS Journal on Computing . 12 (1): 57– 74. doi : 10.1287/ijoc.12.1.57.11901 . ISSN 1091-9856 . 
  7. ↑ Ibarra, Oscar H.; Kim, Chul E. (1975-10-01). "Algoritmos de aproximación rápida para los problemas de la mochila y la suma de subconjuntos" . Journal of the ACM . 22 (4): 463– 468. doi : 10.1145/321906.321909 . ISSN 0004-5411 . S2CID 14619586 .  
  8. ↑ Lawler, Eugene L. (1979-11-01). "Algoritmos de aproximación rápida para problemas de la mochila" . Matemáticas de la investigación operativa . 4 (4): 339– 356. doi : 10.1287/moor.4.4.339 . ISSN 0364-765X . S2CID 7655435 .  
  9. ↑ Rhee, Donguk (2015). Esquemas de aproximación totalmente polinomiales más rápidos para problemas de la mochila (Tesis). Instituto Tecnológico de Massachusetts. hdl : 1721.1/98564 .
  10. ↑ Lawler, Eugene L. (1977-01-01), Hammer, PL; Johnson, EL; Korte, BH; Nemhauser, GL (eds.), "Un algoritmo "pseudopolinomial" para secuenciar trabajos y minimizar la tardanza total**Investigación financiada por la subvención GJ-43227X de la National Science Foundation" , Annals of Discrete Mathematics , Studies in Integer Programming, vol. 1, Elsevier, pp. 331–342 , doi : 10.1016/S0167-5060(08)70742-8 , consultado el 17 de diciembre de 2021.  
  11. ↑ Florian, M.; Lenstra, JK; Rinnooy Kan, AHG (1980-07-01). "Planificación de la producción determinista: algoritmos y complejidad" . Management Science . 26 (7): 669– 679. doi : 10.1287/mnsc.26.7.669 . ISSN 0025-1909 . 
  12. ↑ Lawler, EL (1982-12-01). "Un esquema de aproximación totalmente polinomial para el problema de la tardanza total" . Operations Research Letters . 1 (6): 207– 208. doi : 10.1016/0167-6377(82)90022-0 . ISSN 0167-6377 . 
  13. ↑ van Hoesel, CPM; Wagelmans, APM (2001). "Esquemas de aproximación totalmente polinomiales para problemas de dimensionamiento económico de lotes con capacidad para un solo artículo" . Matemáticas de la investigación operativa . 26 (2): 339– 357. doi : 10.1287/moor.26.2.339.10552 . hdl : 1765/1406 .
  14. ↑ Cai, X. (1995-09-21). "Minimización de la varianza ponderada de forma aceptable en sistemas de una sola máquina" . European Journal of Operational Research . 85 (3): 576– 592. doi : 10.1016/0377-2217(93)E0367-7 . ISSN 0377-2217 . 
  15. ↑ Woeginger, Gerhard J. (1999-05-01). "Un esquema de aproximación para minimizar la varianza ponderada de forma aceptable en una sola máquina" . INFORMS Journal on Computing . 11 (2): 211– 216. doi : 10.1287/ijoc.11.2.211 . ISSN 1091-9856 . 
  16. ↑ Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria , Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi : 10.1007/978-3-642-78240-4 , ISBN   978-3-642-78242-8, MR 1261419 
  17. ↑ Vazirani, Vijay (2001). Algoritmos de aproximación . Berlín: Springer. págs. 69-70 . ISBN  3540653678OCLC 47097680​​ 
  18. ↑ Kellerer, Hans; Pferschy, Ulrich (2004-03-01). "Programación dinámica mejorada en conexión con un FPTAS para el problema de la mochila" . Journal of Combinatorial Optimization . 8 (1): 5– 11. doi : 10.1023/B:JOCO.0000021934.29833.6b . ISSN 1573-2886 . S2CID 36474745 .  
  19. ^ Jin, Ce (2019). "Un FPTAS mejorado para la mochila 0-1" . Procedimientos internacionales de informática de Leibniz (LIPIcs). vol. 132. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 76:1–76:14. arXiv : 1904.09562 . doi : 10.4230/LIPIcs.ICALP.2019.76 . ISBN   9783959771092. S2CID 128317990 . 
  20. ↑ Jansen, Klaus; Kraft, Stefan EJ (2018-02-01). " Un FPTAS más rápido para el problema de la mochila sin límites" . European Journal of Combinatorics . Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller. 68 : 148–174 . arXiv : 1504.04650 . doi : 10.1016/j.ejc.2017.07.016 . ISSN 0195-6698 . S2CID 9557898 .  
  21. ↑ Gribanov, DV (10 de mayo de 2021). "Un FPTAS para el problema de la mochila multidimensional modular $$\var Delta $$". Teoría de la optimización matemática e investigación operativa . Notas de clase en ciencias de la computación. Vol. 12755. págs. 79–95 . arXiv : 2103.07257 . doi : 10.1007/978-3-030-77876-7_6 . ISBN   978-3-030-77875-0. S2CID 232222954 . 
  22. ↑ Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2009-10-01). "Implementación de un fptas eficiente para el problema de la mochila multiobjetivo 0-1" . European Journal of Operational Research . 198 (1): 47– 56. doi : 10.1016/j.ejor.2008.07.047 . ISSN 0377-2217 . 
  23. ↑ Holzhauser, Michael; Krumke, Sven O. (2017-10-01). "Un FPTAS para el problema de la mochila paramétrica" . Information Processing Letters . 126 : 43–47 . arXiv : 1701.07822 . doi : 10.1016/j.ipl.2017.06.006 . ISSN 0020-0190 . S2CID 1013794 .  
  24. ↑ Xu, Zhou (16 de abril de 2012). "Un FPTAS fuertemente polinomial para el problema de la mochila cuadrática simétrica" . European Journal of Operational Research . 218 (2): 377–381 . doi : 10.1016/j.ejor.2011.10.049 . hdl : 10397/24376 . ISSN 0377-2217 . 
  25. ↑ Gopalan, Parikshit; Klivans, Adam; Meka, Raghu; Štefankovic, Daniel; Vempala, Santosh; Vigoda, Eric (1 de octubre de 2011). "Un FPTAS para el problema de la mochila y problemas de conteo relacionados" . Simposio anual IEEE 52.º sobre fundamentos de la informática , 2011. págs. 817-826 . doi : 10.1109/FOCS.2011.32 . ISBN  978-0-7695-4571-4. S2CID 5691574 . 
  26. ↑ Ergun, Funda ; Sinha, Rakesh; Zhang, Lisa (15 de septiembre de 2002). "Un FPTAS mejorado para la ruta más corta restringida" . Information Processing Letters . 83 (5): 287–291 . doi : 10.1016/S0020-0190(02)00205-3 . ISSN 0020-0190 . 
  27. ↑ Tsaggouris, George; Zaroliagis, Christos (2009-06-01). "Optimización multiobjetivo: FPTAS mejorado para rutas más cortas y objetivos no lineales con aplicaciones" . Theory of Computing Systems . 45 (1): 162– 186. doi : 10.1007/s00224-007-9096-4 . ISSN 1433-0490 . S2CID 13010023 .  
  28. ↑ Lin, Chengyu; Liu, Jingcheng; Lu, Pinyan (18 de diciembre de 2013), "Un FPTAS simple para contar cubiertas de aristas" , Actas del Simposio Anual ACM-SIAM de 2014 sobre Algoritmos Discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 341–348 , arXiv : 1309.6115 , doi : 10.1137/1.9781611973402.25 , ISBN  978-1-61197-338-9, S2CID 14598468 , consultado el 13-12-2021 
  29. ↑ Kelmanov, AV; Romanchenko, SM (1 de julio de 2014). "Un FPTAS para un problema de búsqueda de subconjuntos de vectores" . Revista de Matemática Aplicada e Industrial . 8 (3): 329– 336. doi : 10.1134/S1990478914030041 . ISSN 1990-4797 . S2CID 96437935 .  
  30. ↑ Doerr, Benjamin; Eremeev, Anton; Neumann, Frank; Theile, Madeleine; Thyssen, Christian (2011-10-07). "Algoritmos evolutivos y programación dinámica" . Theoretical Computer Science . 412 (43): 6020– 6035. arXiv : 1301.4096 . doi : 10.1016/j.tcs.2011.07.024 . ISSN 0304-3975 . 
  • Complexity Zoo: FPTAS
Lecturas relacionadas
6 articulos
AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...{\estilo de visualización P}Problema de funciónEn la teoría de la complejidad computacional , un problema de función es un problema computacional en el que se espera una única salida (de una fun...{\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}}Optimization problemIn mathematics, engineering, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible ...Esquema de aproximación en tiempo polinomialEsquema de aproximación en tiempo polinomialEn informática (en particular en algoritmia ), un esquema de aproximación de tiempo polinomial ( PTAS ) es un tipo de algoritmo de aproximación par...{\displaystyle n^{2}\times n^{2}}Problema P versus NPEl problema P versus NP es un problema importante sin resolver en la informática teórica . En términos informales, plantea la pregunta de si todo p...{\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }Complejidad parametrizadaEn informática , la complejidad parametrizada es una rama de la teoría de la complejidad computacional que se centra en la clasificación de los pro...