Algoritmo de aproximación parametrizado

Un algoritmo de aproximación parametrizado es un tipo de algoritmo que tiene como objetivo encontrar soluciones aproximadas a problemas de optimización NP-hard en tiempo polinomial en el tamaño de entrada y una función de un parámetro específico. Estos algoritmos están diseñados para combinar los mejores aspectos de los algoritmos de aproximación tradicionales y la manejabilidad de parámetros fijos.

En los algoritmos de aproximación tradicionales, el objetivo es encontrar soluciones que estén a lo sumo un cierto factor α de distancia de la solución óptima, conocida como una α -aproximación, en tiempo polinomial. Por otro lado, los algoritmos parametrizados están diseñados para encontrar soluciones exactas a los problemas, pero con la restricción de que el tiempo de ejecución del algoritmo es polinomial en el tamaño de entrada y una función de un parámetro específico k . El parámetro describe alguna propiedad de la entrada y es pequeño en aplicaciones típicas. Se dice que el problema es manejable con parámetros fijos (FPT) si hay un algoritmo que puede encontrar la solución óptima en el tiempo, donde es una función independiente del tamaño de entrada n . ${\displaystyle f(k)n^{O(1)}}$${\estilo de visualización f(k)}$

Un algoritmo de aproximación parametrizada tiene como objetivo encontrar un equilibrio entre estos dos enfoques mediante la búsqueda de soluciones aproximadas en tiempo FPT: el algoritmo calcula una aproximación α en el tiempo, donde es una función independiente del tamaño de entrada n . Este enfoque tiene como objetivo superar las limitaciones de ambos enfoques tradicionales al tener garantías más sólidas sobre la calidad de la solución en comparación con las aproximaciones tradicionales, al tiempo que sigue teniendo tiempos de ejecución eficientes como en los algoritmos FPT. Se puede encontrar una descripción general del área de investigación que estudia los algoritmos de aproximación parametrizada en la encuesta de Marx ^[1] y la encuesta más reciente de Feldmann et al. ^[2].${\displaystyle f(k)n^{O(1)}}$${\estilo de visualización f(k)}$

El potencial completo de los algoritmos de aproximación parametrizados se utiliza cuando se demuestra que un problema de optimización dado admite un algoritmo de aproximación α que se ejecuta en el tiempo, mientras que, en contraste, el problema no tiene un algoritmo de aproximación α de tiempo polinomial (bajo algún supuesto de complejidad , por ejemplo, ), ni un algoritmo FPT para el parámetro dado k (es decir, es al menos W[1]-duro ). ${\displaystyle f(k)n^{O(1)}}$${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$

Por ejemplo, algunos problemas que son APX-hard y W[1]-hard admiten un esquema de aproximación parametrizado (PAS) , es decir, para cualquier a -aproximación se puede calcular en el tiempo para algunas funciones f y g . Esto entonces evita los límites inferiores en términos de aproximación de tiempo polinomial y manejabilidad de parámetro fijo. Un PAS es similar en espíritu a un esquema de aproximación de tiempo polinomial (PTAS) pero además explota un parámetro dado k . Dado que el grado del polinomio en el tiempo de ejecución de un PAS depende de una función , se supone que el valor de es arbitrario pero constante para que el PAS se ejecute en tiempo FPT. Si esta suposición no es satisfactoria, se trata como un parámetro también para obtener un esquema de aproximación parametrizado eficiente (EPAS) , que para cualquier calcula una -aproximación en el tiempo para alguna función f . Esto es similar en espíritu a un esquema de aproximación de tiempo polinomial eficiente (EPTAS).${\displaystyle \varepsilon >0}$${\displaystyle (1+\varepsilon)}$${\displaystyle f(k,\varepsilon )n^{g(\varepsilon )}}$${\displaystyle g(\varepsilon)}$${\estilo de visualización \varepsilon}$${\estilo de visualización \varepsilon}$ ${\displaystyle \varepsilon >0}$${\displaystyle (1+\varepsilon)}$${\displaystyle f(k,\varepsilon )n^{O(1)}}$

El problema de corte k no tiene un algoritmo de aproximación en tiempo polinomial para ningún , suponiendo y la hipótesis de expansión de conjuntos pequeños . ^[3] También está parametrizado de manera W[1]-dura por el número k de componentes requeridos. ^[4] Sin embargo, existe un EPAS, que calcula una aproximación en el tiempo. ^[5]${\displaystyle (2-\varepsilon)}$${\displaystyle \varepsilon >0}$${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$${\displaystyle (1+\varepsilon)}$${\displaystyle (k/\varepsilon )^{O(k)}n^{O(1)}}$

El problema del árbol de Steiner es FPT parametrizado por el número de terminales. ^[6] Sin embargo, para el parámetro "dual" que consiste en el número k de no terminales contenidos en la solución óptima, el problema es W[2]-hard (debido a una reducción del folclore del problema del conjunto dominante ). También se sabe que el árbol de Steiner es APX-hard . ^[7] Sin embargo, hay un EPAS que calcula una -aproximación en el tiempo. ^[8] El problema más general del bosque de Steiner es NP-hard en grafos de ancho de árbol 3. Sin embargo, en grafos de ancho de árbol t un EPAS puede calcular una -aproximación en el tiempo. ^[9]${\displaystyle (1+\varepsilon)}$${\displaystyle 2^{O(k^{2}/\varepsilon ^{4})}n^{O(1)}}$ ${\displaystyle (1+\varepsilon)}$${\displaystyle 2^{O({\frac {t^{2}}{\varepsilon }}\log {\frac {t}{\varepsilon }})}n^{O(1)}}$

Se sabe que el problema del subgrafo de Steiner fuertemente conectado está parametrizado de manera W[1]-dura por el número k de terminales, ^[10] y tampoco admite una aproximación en tiempo polinomial (bajo supuestos de complejidad estándar ). ^[11] Sin embargo, se puede calcular una aproximación 2 en el tiempo. ^[12] Además, esto es lo mejor posible, ya que no se puede calcular ninguna aproximación en el tiempo para ninguna función f , bajo Gap- ETH . ^[13]${\displaystyle O(\log ^{2-\varepsilon }n)}$$Estilo de visualización 3 k n O(1)$${\displaystyle (2-\varepsilon)}$${\displaystyle f(k)n^{O(1)}}$

Para los problemas de agrupamiento métrico bien estudiados de k -mediana y k -medias parametrizadas por el número k de centros, se sabe que no se puede calcular ninguna aproximación para k-mediana ni ninguna aproximación para k-medias en el tiempo para ninguna función f , bajo Gap- ETH . ^[14] Existen algoritmos de aproximación parametrizada coincidentes, ^[14] pero no se sabe si las aproximaciones coincidentes se pueden calcular en tiempo polinomial. ${\displaystyle (1+2/e-\varepsilon )}$${\displaystyle (1+8/e-\varepsilon )}$${\displaystyle f(k)n^{O(1)}}$

La agrupación se considera a menudo en entornos de datos de baja dimensión y, por lo tanto, una parametrización prácticamente relevante es por la dimensión de la métrica subyacente . En el espacio euclidiano , los problemas k-Mediana y k-Media admiten un EPAS parametrizado por la dimensión d , ^{[15] [16]} y también un EPAS parametrizado por k . ^{[17] [18]} El primero se generalizó a un EPAS para la parametrización por la dimensión de duplicación . ^{[19] Para el parámetro} de dimensión de autopista vagamente relacionado , hasta la fecha solo se conoce un esquema de aproximación con tiempo de ejecución XP . ^[20]

Para el problema de k -centros métricos , se puede calcular una 2-aproximación en tiempo polinomial. Sin embargo, cuando se parametriza por el número k de centros, ^[21] la dimensión de duplicación (de hecho, la dimensión de una métrica de Manhattan ), ^[22] o la dimensión de la autopista , ^[21] no existe ningún algoritmo de -aproximación parametrizado , bajo supuestos de complejidad estándar . Además, el problema de k-centros es W[1]-duro incluso en grafos planares cuando se parametriza simultáneamente por el número k de centros, la dimensión de duplicación , la dimensión de la autopista , y el ancho del camino . ^[23] Sin embargo, cuando se combina k con la dimensión de duplicación existe un EPAS, ^[23] y lo mismo es cierto cuando se combina k con la dimensión de la autopista . ^[24] Para la versión más general con capacidades de vértice, existe un EPAS para la parametrización por k y la dimensión de duplicación, pero no cuando se usa k y la dimensión de la autopista como parámetro. ^[25] En cuanto al ancho de ruta, k-Center admite un EPAS incluso para el parámetro de ancho de árbol más general , y también para el ancho de clique . ^[26]${\displaystyle (2-\varepsilon )}$

Una variante de optimización del problema k -Clique es el problema del k -subgrafo más denso (que es un problema de satisfacción de restricciones 2-ario ), donde la tarea es encontrar un subgrafo en k vértices con el máximo número de aristas. No es difícil obtener una aproximación simplemente eligiendo una coincidencia de tamaño en el grafo de entrada dado, ya que el máximo número de aristas en k vértices es siempre como máximo . Esto también es asintóticamente óptimo, ya que bajo Gap- ETH no se puede calcular ninguna aproximación en tiempo FPT parametrizado por k . ^[27]${\displaystyle (k-1)}$${\displaystyle k/2}$${\displaystyle {k \choose 2}=k(k-1)/2}$${\displaystyle k^{1-o(1)}}$

Para el problema del conjunto dominante es W[1]-difícil calcular cualquier aproximación en el tiempo para cualquier función g y f . ^[28]${\displaystyle g(k)}$${\displaystyle f(k)n^{O(1)}}$

La kernelización es una técnica utilizada en la manejabilidad de parámetros fijos para preprocesar una instancia de un problema NP-hard con el fin de eliminar las "partes fáciles" y revelar el núcleo NP-hard de la instancia. Un algoritmo de kernelización toma una instancia I y un parámetro k , y devuelve una nueva instancia con un parámetro tal que el tamaño de y está acotado como una función del parámetro de entrada k , y el algoritmo se ejecuta en tiempo polinomial. Un algoritmo de kernelización α -aproximado es una variación de esta técnica que se utiliza en algoritmos de aproximación parametrizados. Devuelve un núcleo tal que cualquier β -aproximación en puede convertirse en una αβ -aproximación a la instancia de entrada I en tiempo polinomial. Esta noción fue introducida por Lokshtanov et al., ^[29] pero existen otras nociones relacionadas en la literatura como los núcleos de Turing ^[30] y la kernelización de fidelidad α . ^[31]${\displaystyle I'}$${\displaystyle k'}$${\displaystyle I'}$${\displaystyle k'}$${\displaystyle I'}$${\displaystyle I'}$

En cuanto a los núcleos regulares (no aproximados), un problema admite un algoritmo de kernelización α-aproximado si y solo si tiene un algoritmo de aproximación α parametrizado. La prueba de este hecho es muy similar a la de los núcleos regulares . ^[29] Sin embargo, el núcleo aproximado garantizado podría ser de tamaño exponencial (o peor) en el parámetro de entrada. Por lo tanto, se vuelve interesante encontrar problemas que admitan núcleos aproximados de tamaño polinomial. Además, un esquema de kernelización aproximada de tamaño polinomial (PSAKS) es un algoritmo de kernelización α -aproximado que calcula un núcleo de tamaño polinomial y para el cual α puede establecerse en para cualquier . ${\displaystyle 1+\varepsilon }$${\displaystyle \varepsilon >0}$

Por ejemplo, mientras que el problema de la cobertura de vértices conectados es FPT parametrizado por el tamaño de la solución, no admite un núcleo de tamaño polinomial (regular) (a menos que ), pero existe un PSAKS. ^[29] De manera similar, el problema del árbol de Steiner es FPT parametrizado por el número de terminales, no admite un núcleo de tamaño polinomial (a menos que ), pero existe un PSAKS. ^[29] Al parametrizar el árbol de Steiner por el número de no terminales en la solución óptima, el problema es W[2]-hard (y por lo tanto no admite ningún núcleo exacto, a menos que FPT=W[2]), pero aún admite un PSAKS. ^[8]${\displaystyle {\textsf {NP}}\subseteq {\textsf {coNP/poly}}}$${\displaystyle {\textsf {NP}}\subseteq {\textsf {coNP/poly}}}$

• Daniel Lokshtanov: Un esquema de aproximación parametrizado para el corte k-Min
• Tuukka Korhonen: Algoritmo de aproximación 2 de tiempo exponencial único para el ancho de árbol
• Karthik CS: Resultados recientes de la dureza de aproximación en complejidad parametrizada
• Ariel Kulik. Relaciones de recurrencia de dos variables con aplicación a aproximaciones parametrizadas
• Meirav Zehavi. Aproximación de FPT
• Vincent Cohen-Añadido: Sobre la complejidad parametrizada de varios problemas de agrupamiento
• Fahad Panolan. Aproximación parametrizada para un conjunto independiente de rectángulos
• Andreas Emil Feldmann. Esquemas aproximados de kernelización para redes Steiner