Esquema de aproximación en tiempo totalmente polinomial

Un esquema de aproximación en 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 menos multiplicado por el valor correcto y, como máximo, el valor correcto. ${\displaystyle 1-\varepsilon }$ ${\displaystyle 1+\varepsilon }$

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 a entender que un FPTAS debería producir una solución válida (y no sólo el valor de la solución). Devolver un valor y encontrar una solución con ese valor son equivalentes suponiendo que el problema posee autoreducibilidad .

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 general de aproximación de tiempo polinomial (PTAS). El tiempo de ejecución de un PTAS general es polinómico en el tamaño del problema para cada ε específico, pero puede ser exponencial en 1/ε. ^[1]

El término FPTAS también puede usarse para referirse a la clase de problemas que tiene 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 manejables con parámetros fijos con respecto a la parametrización estándar. ^[3]

Cualquier problema de optimización fuertemente NP-duro con una función objetivo acotada polinomialmente no puede tener un FPTAS a menos que P=NP. ^[4] Sin embargo, lo contrario falla: por ejemplo, si P no es igual a NP, la mochila con dos restricciones no es fuertemente NP-dura, pero no tiene FPTAS incluso cuando el objetivo óptimo está acotado polinomialmente. ^[5]

Convertir 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á formada por n vectores, x ₁ ,..., x _n .
• Cada vector de entrada está formado por algunos números enteros no negativos, donde puede depender de la entrada. ${\displaystyle a}$ ${\displaystyle a}$
• Todos los componentes de los vectores de entrada están codificados en binario. Entonces el tamaño del problema es O( n +log( X )), donde X es la suma de todos los componentes de todos los vectores.

Programa dinámico extremadamente simple

Se supone que el problema tiene un algoritmo de programación dinámica (DP) que utiliza estados . Cada estado es un vector formado por algunos números enteros no negativos, donde 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 Si _. Cada estado codifica una solución parcial al problema, utilizando entradas x ₁ ,..., x _i . Los componentes del PD son: ${\displaystyle b}$ ${\displaystyle b}$

• Un conjunto S ₀ 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 del DP es:

• Sea S ₀  := el conjunto de estados iniciales.
• Para k = 1 an hacer :
  • Sea S _k  := { f ( s , x _k ) | f en F , s en S _{k −1} }
• Salida mín/máx {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 estar en O( n V ^b ), donde V es el entero más grande que puede aparecer en un estado. Si V está en O ( X ), entonces el tiempo de ejecución está en O ( n X ^b ), que es solo tiempo pseudopolinomial , ya que es exponencial en el tamaño del problema que está en O (log X ).

La forma de hacerlo polinomio es recortar el espacio de estados : en lugar de mantener todos los estados posibles en cada paso, mantenga solo un subconjunto de los estados; eliminar estados que estén "suficientemente cerca" de otros estados. Bajo ciertas condiciones, este recorte se puede realizar de manera que no cambie demasiado el valor objetivo.

Para formalizar esto, asumimos que el problema que nos ocupa tiene un vector entero no negativo d = ( d ₁ ,..., d _b ), llamado vector de grados del problema. Para cada número real r >1, decimos que dos vectores de estado s ₁ , s ₂ son (d,r)-cercanos si, para cada coordenada j en 1,..., b : (en particular, si d _j =0 para algunos j , entonces ). ${\displaystyle r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}}$ ${\displaystyle s_{1,j}=s_{2,j}}$

Un problema se considera extremadamente benévolo si satisface las tres condiciones siguientes:

1. La proximidad se preserva 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 dos vectores de estado cualesquiera s ₁ , s ₂ , se cumple lo siguiente: si s ₁ es ( d,r )-cerca de s ₂ , entonces f ( s ₁ , x ) es ( d,r )-cerca de f ( s ₂ ,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 , denota por f _j (s,x) la j -ésima coordenada de f . Esta f _j puede verse como una función entera en variables b + a . Supongamos que cada f _j es un polinomio con coeficientes no negativos. Conviértalo a 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 preserva mediante la función de valor : existe un número entero G ≥ 0 (que es una función de la función de valor g y el vector de grados d ), tal que para cualquier r >1, y para dos vectores de estado cualesquiera s ₁ , s ₂ , se cumple lo siguiente: si s ₁ es ( d,r ) cercano a s ₂ , entonces: g ( s ₁ ) ≤ r ^G · g ( s ₂ ) (en problemas de minimización); g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (en problemas de maximización).
   • Una condición suficiente para esto 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 se pueden evaluar en politiempo.
   • El número | F | de funciones de transición es polinomio en n y log( X ).
   • El conjunto S ₀ de estados iniciales se puede calcular en tiempo polinómico 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 ₁ (n,log(X)).
   • Si d _j =0, la cardinalidad de V _j es como máximo un polinomio P ₂ ( n ,log( X )).

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

• ${\displaystyle \epsilon }$ := la relación de aproximación requerida.
• ${\displaystyle r:=1+{\frac {\epsilon }{2Gn}}}$, donde G es la constante de la condición 2. Tenga en cuenta que . ${\displaystyle {\frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}}$
• ${\displaystyle L:=\left\lceil {\frac {P_{1}(n,\log(X))}{\ln(r)}}\right\rceil }$, donde P ₁ es el polinomio de la condición 3 (un límite superior en el ln de cada valor que puede aparecer en un vector de estado). Tenga en cuenta que , por lo tanto, es polinomio en el tamaño de la entrada y en . Además, por definición de P ₁ , cada número entero que puede aparecer en un vector de estado está en el rango [0, r ^L ]. ${\displaystyle L\leq \left\lceil \left(1+{\frac {2Gn}{\epsilon }}\right)P_{1}(n,\log {X})\right\rceil }$ ${\displaystyle 1/\epsilon }$ ${\displaystyle r^{L}=e^{\ln {r}}\cdot L\geq e^{P_{1}(n,\log {x})}}$
• Divida el rango [0, r ^L ] en L +1 r -intervalos: . ${\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-cuadros : cada coordenada k con grado d _k ≥ 1 se divide en los intervalos L +1 anteriores; cada coordenada con d _k = 0 se divide en P ₂ ( n , log ( X ) ) intervalos singleton: un intervalo para cada valor posible de la coordenada k (donde P ₂ es el polinomio de la condición 3 anterior).
  • Tenga en cuenta que cada estado posible está contenido exactamente en un r -box; si dos estados están en el mismo r -box, entonces están ( d , r )-cerca.
• ${\displaystyle R:=(L+1+P_{2}(n,\log {X}))^{b}}$.
  • Tenga en cuenta que el número de r -boxes es como máximo R . Dado que b es una constante fija, este R es polinomio en el tamaño de la entrada y en . ${\displaystyle 1/\epsilon }$

El FPTAS se ejecuta de manera similar al DP, pero en cada paso, recorta el conjunto de estados en un conjunto más pequeño T _k , que contiene exactamente un estado en cada r -box. El algoritmo del FPTAS es:

• Sea T ₀  := S ₀ = el conjunto de estados iniciales.
• Para k = 1 an hacer :
  • 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 -box que contenga uno o más estados de U _k , mantenga exactamente un estado en T _k .
• Salida mín/máx {g(s) | s en T _n }.

El tiempo de ejecución del FPTAS es polinomio en el número total de estados posibles en cada Ti , que es como máximo el número total de _r -cajas , que es como máximo R , que es polinomio en n , log( X ), y . ${\displaystyle 1/\epsilon }$

Tenga en cuenta que, para cada estado su en U _{k ,} su subconjunto T _k contiene al menos un estado _st que es (d,r) cercano a su _. Además, cada U _k es un subconjunto de S _k en el DP original (sin recortar). El lema principal para demostrar la exactitud 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 es ( d , rk ⁾ cercano a s _s .

La prueba 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 es válido 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 . Según el supuesto de inducción, hay un estado s _t- en T _k-1 , es decir ( d , r ^k-1 ) -cercano a s _{s −} . Dado que las transiciones preservan la proximidad (Condición 1 anterior), f ( s _{t −} , x ) es ( d , r ^k-1 ) -cerca de f ( s _{s −} , x )= s _s . Este f ( s _{t −} , x ) está en U _k . Después del recorte, hay un estado _st en T k _que es ( d , r ) cercano a f(s _t- ,x) . Este s _t es ( d , rk ⁾ -cerca de s _s .

Consideremos ahora el estado s ^* en S _n , que corresponde a la solución óptima (es decir, g ( s* )=OPT). Según el lema anterior, hay un estado t * en T _n , que es ( d , r ⁿ ) cercano a s ^* . Dado que la función de valor preserva la proximidad, g (t*) ≥ r ^(-Gn) · g ( s* ) para un problema de maximización. Por definición de r ,. Entonces . Un argumento similar funciona para un problema de minimización. ${\displaystyle r^{-Gn}\geq (1-\epsilon )}$ ${\displaystyle g(t^{*})\geq (1-\epsilon )\cdot OPT}$

Ejemplos

A continuación se muestran algunos ejemplos de problemas extremadamente benévolos que tienen un FPTAS según el teorema anterior. ^[6]

1. La partición de números de múltiples vías (equivalentemente, programación de máquinas idénticas ) con el objetivo de minimizar la suma más grande es extremadamente benévola. Aquí, tenemos a = 1 (las entradas son números enteros) y b = el número de contenedores (que se considera fijo). Cada estado es un vector de b números enteros que representan las sumas de los b contenedores. Hay b funciones: cada función j representa insertar la siguiente entrada en bin j . La función g ( s ) elige el elemento más grande de s . S ₀ = {(0,...,0)}. Las condiciones para la benevolencia extrema se satisfacen con el vector de grados 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|| o Qm|| o Salón|| . ${\displaystyle \max C_{j}}$ ${\displaystyle \max C_{j}}$ ${\displaystyle \max C_{j}}$

• Nota : considere el caso especial b =2, donde el objetivo es minimizar el cuadrado de la diferencia entre las sumas de las dos partes. Se puede utilizar el mismo DP, pero esta vez con la función de valor g ( s ) = ( s ₁ - s ₂ ) ² . Ahora, se viola la condición 2: los estados ( s ₁ , s ₁ ) y ( s ₁ , s ₂ ) pueden ser ( d,r )-cercanos, pero g ( s ₁ , s ₁ ) = 0 mientras que g ( s ₁ , s ₂ ) > 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 politiempo 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; este último indicado por Qm|| - es ex-benevolente con a =1, b =3, d=(1,1,3). Puede ampliarse a cualquier potencia fija del tiempo de finalización. ${\displaystyle \sum C_{j}^{3}}$

3. Suma del tiempo de finalización ponderado en cualquier número fijo de máquinas idénticas o uniformes; estas últimas se denotan por Qm|| . ${\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|time-dep| . Esto es válido incluso para la suma ponderada del tiempo de finalización. ${\displaystyle \sum C_{j}}$

5. Anticipación-tardía ponderada sobre una fecha de vencimiento común en cualquier número fijo de máquinas: m|| . ${\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 sólo si la activación de la transición f _i en este par conduciría a un estado válido.
• Una relación de dominancia , que es un orden parcial sobre los estados (no hay indiferencias, no todos los pares son comparables), y una relación de cuasi-dominancia que es un preorden total sobre los estados (se permiten indiferencias, todos los pares son comparables).

El DP original se modifica de la siguiente manera:

• Sea S ₀  := el conjunto de estados iniciales.
• Para k = 1 an hacer :
  • 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 mín/máx {g(s) | s en S _n }.

Un problema se llama benévolo si satisface las siguientes condiciones (que amplían las condiciones 1, 2, 3 anteriores):

1. La proximidad se preserva 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 dos vectores de estado cualesquiera s ₁ , s ₂ , se cumple lo siguiente:
   • si s ₁ es ( d,r ) cercano a s ₂ y s ₁ casi domina a s ₂ , entonces (a) f ( s ₁ , x ) es ( d,r ) cercano a f ( s ₂ , x ), y f ( s ₁ , x ) casi domina a f ( s ₂ ,x ) , o (b) f ( s ₁ , x ) domina a f ( s ₂ ,x ).
   • si s ₁ domina a s ₂ , entonces f ( s ₁ , x ) domina a f ( s ₂ ,x ).
2. La proximidad se preserva mediante la función de valor: existe un número entero G ≥ 0 (una función de la función de valor g y el vector de grados d ), tal que para cualquier r >1, y para dos vectores de estado cualesquiera s ₁ , s ₂ , se cumple lo siguiente:
   • si s ₁ es ( d,r ) cercano a s ₂ y s ₁ casi domina a s ₂ , entonces: g ( s ₁ ) ≤ r ^G · g ( s ₂ ) (en problemas de minimización); g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (en problemas de maximización).
   • si s ₁ domina a s ₂ , entonces g ( s ₁ ) ≤ g ( s ₂ ) (en problemas de minimización); g ( s ₁ ) ≥ g ( s ₂ ) (en problemas de maximización).
3. Condiciones técnicas (además de las anteriores):
   • La relación de cuasi-dominancia se puede decidir 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 dos vectores de estado cualesquiera s ₁ , s ₂ , se cumple lo siguiente:
   • si s ₁ es ( d,r ) cercano a s ₂ , y s ₁ casi domina a s ₂ , entonces h ( s ₁ , x ) ≥ h ( s ₂ , x ) .
   • si s ₁ domina a s ₂ , entonces h ( s ₁ , x ) ≥ h ( s ₂ , x ).

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

• Sea T ₀  := S ₀ = el conjunto de estados iniciales.
• Para k = 1 an hacer :
  • 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 -box que contenga uno o más estados de U _k , elija un único elemento que cuasi domine todos los demás elementos en U _k e insértelo en T _k .
• Salida mín/máx {g(s) | s en T _n }.

Ejemplos

A continuación se muestran algunos ejemplos de problemas benévolos que tienen un FPTAS según el teorema anterior. ^[6]

1. El problema de la mochila 0-1 es benévolo. Aquí tenemos un =2: cada entrada es un vector de 2 (peso, valor). Hay un DP con b =2: cada estado codifica (peso actual, valor actual). Hay dos funciones de transición: f ₁ corresponde a agregar el siguiente elemento de entrada y f ₂ corresponde a no agregarlo. Las funciones de filtro correspondientes son: h ₁ verifica que el peso con el siguiente artículo de entrada sea como máximo la capacidad de la mochila; h ₂ siempre devuelve Verdadero. La función de valor g ( s ) devuelve s ₂ . El conjunto de estados inicial es {(0,0)}. El vector de grados 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 t iff s ₁ ≤ t ₁ . La implicación de esto es que, si el estado t tiene un peso mayor que el estado s , entonces se permite que las funciones de transición no preserven la proximidad entre t y s (es posible, por ejemplo, que s tenga un sucesor y t no). tener un sucesor correspondiente). Ibarra y Kim presentaron anteriormente un algoritmo similar. ^[7] El tiempo de ejecución de este FPTAS se puede mejorar para operaciones con números enteros. ^[8] El exponente se mejoró posteriormente a 2,5. ^[9] ${\displaystyle O(n\log {1/\epsilon }+1/\epsilon ^{4})}$

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

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|| . ${\displaystyle \sum w_{j}U_{j}}$

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

4. Número de trabajos deteriorados en una sola máquina: 1|deteriorarse| . ${\displaystyle \max C_{j}}$

5. Total de trabajos retrasados ​​en una sola máquina: 1|| . ${\displaystyle \sum V_{j}}$

6. Total de trabajos retrasados ​​ponderados en una sola máquina: 1|| . ${\displaystyle \sum w_{j}V_{j}}$

No ejemplos

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

1. En el problema de tardanza total 1|| , la formulación de programación dinámica de Lawler ^[10] requiere actualizar todos los estados en el antiguo espacio de estados algunas B veces, donde B es del orden de X (el tamaño máximo de entrada). Lo mismo se aplica a un PD 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 el log( X ), por lo que se viola la segunda condición técnica. La técnica de recorte de estado no es útil, pero se ha utilizado otra técnica, el redondeo de entrada, para diseñar un FPTAS. ^{[12] [13]} ${\displaystyle \sum T_{j}}$

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

FPTAS para aproximar números reales

Un tipo diferente de problema en el que FPTAS puede resultar útil es encontrar números racionales que se aproximen a algunos números reales. Por ejemplo, considere la serie infinita . La suma es un número irracional . Para aproximarlo por 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 de aproximadamente . Por lo tanto, para obtener un error de ε, necesitamos aproximadamente elementos, por lo que este es un FPTAS. Tenga en cuenta que esta suma particular se puede representar mediante otra suma en la que solo se necesitan elementos O(log(ε)), por lo que la suma se puede aproximar en tiempo polinomial en la longitud de codificación de ε. ^{[16] : 35, Sección 1} ${\displaystyle \sum _{i=1}^{\infty }{\frac {1}{i^{3}}}}$ ${\displaystyle {\frac {1}{2k^{2}}}}$ ${\displaystyle {\sqrt {\frac {1}{2\epsilon }}}}$

Algunos otros problemas que tiene un FPTAS

• El problema de la mochila , ^{[17] [18]} así como algunas de sus variantes:
  • 0-1 Problema de mochila. ^[19]
  • Problema de mochila ilimitado. ^[20]
  • Problema de mochila multidimensional con restricciones modulares delta. ^[21]
  • Problema de mochila multiobjetivo 0-1. ^[22]
  • Problema de mochila paramétrica. ^[23]
  • Problema de mochila cuadrática simétrica. ^[24]
• Count-subset-sum (# SubsetSum ): encontrar el número de subconjuntos distintos con una suma de como máximo C. ^[25]
• Ruta más corta restringida : encontrar una ruta de costo mínimo entre dos nodos en un gráfico, sujeta a una restricción de retraso. ^[26]
• Caminos más cortos y objetivos no lineales. ^[27]
• Contando cubiertas de bordes . ^[28]
• Problema de búsqueda de subconjuntos de vectores donde la dimensión es fija. ^[29]

Ver también

• Los "programas dinámicos benévolos", 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 aproximación , 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.), Conferencias sobre algoritmos de aproximación y verificación de pruebas , Apuntes de conferencias sobre informática, vol. 1367, Springer, págs. 5–28, doi :10.1007/BFb0053011, ISBN 9783540642015. Véase la discusión que sigue a la Definición 1.30 en la p. 20.
3. Cai, encalado; Chen, Jianer (junio de 1997). "Sobre la trazabilidad y aproximabilidad de parámetros fijos de los problemas de optimización de NP". Revista de Ciencias de la Computación y de Sistemas . 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 con la mochila . Saltador. Teorema 9.4.1.
6. Woeginger, Gerhard J. (1 de febrero de 2000). "¿Cuándo garantiza una formulación de programación dinámica la existencia de un esquema de aproximación de tiempo totalmente polinomial (FPTAS)?". Revista INFORMA de Informática . 12 (1): 57–74. doi :10.1287/ijoc.12.1.57.11901. ISSN  1091-9856.
7. Ibarra, Óscar H.; Kim, Chul E. (1 de octubre de 1975). "Algoritmos de aproximación rápida para problemas de mochila y suma de subconjuntos". Revista de la ACM . 22 (4): 463–468. doi : 10.1145/321906.321909 . ISSN  0004-5411. S2CID  14619586.
8. Lawler, Eugene L. (1 de noviembre de 1979). "Algoritmos de aproximación rápida para problemas de mochila". Matemáticas de la Investigación de Operaciones . 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 mochila (tesis de tesis). Instituto de Tecnología de Massachusetts. hdl :1721.1/98564.
10. Lawler, Eugene L. (1 de enero de 1977), Hammer, PL; Johnson, EL; Korte, BH; Nemhauser, GL (eds.), "Un algoritmo "pseudopolinomial" para secuenciar trabajos para minimizar las tardanzas totales**Investigación respaldada por la subvención GJ-43227X de la Fundación Nacional de Ciencias", Annals of Discrete Mathematics , Studies in Integer Programming, vol. 1, Elsevier, págs. 331–342, doi :10.1016/S0167-5060(08)70742-8 , consultado el 17 de diciembre de 2021
11. Florián, M.; Lenstra, JK; Rinnooy Kan, AHG (1 de julio de 1980). "Planificación determinista de la producción: algoritmos y complejidad". Ciencias de la gestión . 26 (7): 669–679. doi :10.1287/mnsc.26.7.669. ISSN  0025-1909.
12. Lawler, EL (1 de diciembre de 1982). "Un esquema de aproximación totalmente polinomial para el problema de la tardanza total". Cartas de investigación operativa . 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 polinómica para problemas de tamaño de lotes económicos capacitados para un solo elemento". Matemáticas de la Investigación de Operaciones . 26 (2): 339–357. doi : 10.1287/moor.26.2.339.10552.
14. Cai, X. (21 de septiembre de 1995). "Minimización de la variación ponderada agradable en sistemas de una sola máquina". Revista europea de investigación operativa . 85 (3): 576–592. doi :10.1016/0377-2217(93)E0367-7. ISSN  0377-2217.
15. Woeginger, Gerhard J. (1 de mayo de 1999). "Un esquema de aproximación para minimizar la variación ponderada agradablemente en una sola máquina". Revista INFORMA de Informática . 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, señor  1261419
17. Vazirani, Vijay (2001). Algoritmos de aproximación . Berlín: Springer. págs. 69–70. ISBN 3540653678. OCLC  47097680.
18. Kellerer, Hans; Pferschy, Ulrich (1 de marzo de 2004). "Programación dinámica mejorada en conexión con un FPTAS para el problema de la mochila". Revista de optimización combinatoria . 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 (1 de febrero de 2018). "Un FPTAS más rápido para el problema ilimitado de las mochilas". Revista europea de combinatoria . Algoritmos combinatorios, dedicados a la memoria de 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 mochila multidimensional modular $$\var Delta $$". Teoría de la Optimización Matemática e Investigación de Operaciones . Apuntes de conferencias sobre informática. 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. Bazgán, Cristina; Hugot, Adriano; Vanderpooten, Daniel (1 de octubre de 2009). "Implementación de fptas eficientes para el problema de la mochila multiobjetivo 0-1". Revista europea de investigación operativa . 198 (1): 47–56. doi :10.1016/j.ejor.2008.07.047. ISSN  0377-2217.
23. Holzhauser, Michael; Krumke, Sven O. (1 de octubre de 2017). "Un FPTAS para el problema de la mochila paramétrica". Cartas de procesamiento de información . 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 mochila cuadrática simétrica". Revista europea de investigación operativa . 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 #Knapsack y problemas de conteo relacionados". 2011 52º Simposio Anual del IEEE sobre Fundamentos de la Informática . 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". Cartas de procesamiento de información . 83 (5): 287–291. doi :10.1016/S0020-0190(02)00205-3. ISSN  0020-0190.
27. Tsaggouris, George; Zaroliagis, Christos (1 de junio de 2009). "Optimización multiobjetivo: FPTAS mejorado para caminos más cortos y objetivos no lineales con aplicaciones". Teoría de los Sistemas Computacionales . 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 bordes", Actas del Simposio anual ACM-SIAM de 2014 sobre algoritmos discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 348, arXiv : 1309.6115 , doi : 10.1137/1.9781611973402.25, ISBN 978-1-61197-338-9, S2CID  14598468 , consultado el 13 de diciembre de 2021
29. Kel'manov, 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, Benjamín; Eremeev, Antón; Neumann, Frank; Theile, Madeleine; Thyssen, cristiano (7 de octubre de 2011). "Algoritmos evolutivos y programación dinámica". Informática Teórica . 412 (43): 6020–6035. arXiv : 1301.4096 . doi : 10.1016/j.tcs.2011.07.024 . ISSN  0304-3975.

enlaces externos

• Zoológico de Complejidad: FPTAS