Hispanopedia Wiki
Articulo de referencia

Algoritmo de aproximación parametrizado

Un algoritmo de aproximación parametrizado es un tipo de algoritmo que busca encontrar soluciones aproximadas a problemas de optimización NP-difíciles en tiempo polinomial, en f...

Hispanopedia WikiContenido en espanolLectura gratuita

Un algoritmo de aproximación parametrizado es un tipo de algoritmo que busca encontrar soluciones aproximadas a problemas de optimización NP-difíciles en tiempo polinomial, en función del tamaño de la entrada y de un parámetro específico. Estos algoritmos están diseñados para combinar las mejores características de los algoritmos de aproximación tradicionales y la facilidad de resolución con parámetros fijos.

En los algoritmos de aproximación tradicionales, el objetivo es encontrar soluciones que estén como máximo a un cierto factor α de la solución óptima, conocida como aproximación α , en tiempo polinomial. Por otro lado, los algoritmos parametrizados están diseñados para encontrar soluciones exactas a problemas, pero con la restricción de que el tiempo de ejecución del algoritmo sea polinomial en el tamaño de la 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 tratable con parámetros fijos (FPT) si existe un algoritmo que puede encontrar la solución óptima enF(k)norteO(1){\displaystyle f(k)n^{O(1)}}tiempo, dondeF(k){\displaystyle f(k)}es una función independiente del tamaño de entrada n .

Un algoritmo de aproximación parametrizado tiene como objetivo encontrar un equilibrio entre estos dos enfoques al encontrar soluciones aproximadas en tiempo FPT: el algoritmo calcula una α -aproximación enF(k)norteO(1){\displaystyle f(k)n^{O(1)}}tiempo, dondeF(k){\displaystyle f(k)}es una función independiente del tamaño de entrada n . Este enfoque busca superar las limitaciones de los enfoques tradicionales al ofrecer mayores garantías sobre la calidad de la solución en comparación con las aproximaciones tradicionales, manteniendo al mismo tiempo tiempos de ejecución eficientes como en los algoritmos FPT. Una visión general del área de investigación que estudia los algoritmos de aproximación parametrizados se puede encontrar en el estudio de Marx [ 1 ] y en el estudio más reciente de Feldmann et al. [ 2 ].

Relaciones de aproximación obtenibles

Se aprovecha todo el potencial de los algoritmos de aproximación parametrizados cuando se demuestra que un problema de optimización dado admite un algoritmo de aproximación α que se ejecuta enF(k)norteO(1){\displaystyle f(k)n^{O(1)}}tiempo, mientras que en contraste el problema tampoco tiene un algoritmo de aproximación α de tiempo polinomial (bajo alguna suposición de complejidad , por ejemplo,PAG≠nortePAG{\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}), ni un algoritmo FPT para el parámetro k dado (es decir, es al menos W[1]-difícil ).

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

k -Corte

El problema del k -corte no tiene tiempo polinomial(2−ε){\displaystyle (2-\varepsilon )}-algoritmo de aproximación para cualquierε>0{\displaystyle \varepsilon >0}, suponiendoPAG≠nortePAG{\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}y la hipótesis de expansión de conjuntos pequeños . [ 3 ] También es W[1]-difícil parametrizado por el número k de componentes requeridos. [ 4 ] Sin embargo, existe un EPAS que calcula un(1+ε){\displaystyle (1+\varepsilon )}-aproximación en(k/ε)O(k)norteO(1){\displaystyle (k/\varepsilon )^{O(k)}n^{O(1)}}tiempo. [ 5 ]

Vendedor ambulante

El problema del viajante es APX-difícil y paraNP-difícil parametrizado por la dimensión de duplicación (ya que es NP-difícil en el plano euclidiano ). Sin embargo, existe un EPAS parametrizado por la dimensión de duplicación , e incluso para el parámetro de dimensión de autopista más general . [ 6 ]

Árbol Steiner

El problema del árbol de Steiner es FPT parametrizado por el número de terminales. [ 7 ] 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]-difícil (debido a una reducción popular del problema del conjunto dominante ). También se sabe que el árbol de Steiner es APX-difícil . [ 8 ] Sin embargo, existe un EPAS que calcula un(1+ε){\displaystyle (1+\varepsilon )}-aproximación en2O(k2/ε4)norteO(1){\displaystyle 2^{O(k^{2}/\varepsilon ^{4})}n^{O(1)}}tiempo. [ 9 ] El problema más general del bosque de Steiner es NP-difícil en grafos de ancho de árbol 3. Sin embargo, en grafos de ancho de árbol t, un EPAS puede calcular un(1+ε){\displaystyle (1+\varepsilon )}-aproximación en2O(t2εregistro⁡tε)norteO(1){\displaystyle 2^{O({\frac {t^{2}}{\varepsilon }}\log {\frac {t}{\varepsilon }})}n^{O(1)}}tiempo. [ 10 ]

Subgrafo de Steiner fuertemente conectado

Se sabe que el problema del subgrafo de Steiner fuertemente conectado es W[1]-difícil parametrizado por el número k de terminales, [ 11 ] y tampoco admite unO(registro2−ε⁡norte){\displaystyle O(\log ^{2-\varepsilon }n)}-aproximación en tiempo polinomial (bajo supuestos de complejidad estándar ). [ 12 ] Sin embargo, se puede calcular una 2-aproximación en3knorteO(1){\displaystyle 3^{k}n^{O(1)}}tiempo. [ 13 ] Además, esto es lo mejor posible, ya que no(2−ε){\displaystyle (2-\varepsilon )}-la aproximación se puede calcular enF(k)norteO(1){\displaystyle f(k)n^{O(1)}}tiempo para cualquier función f , bajo Gap- ETH . [ 14 ]

k -Mediana y k -Media

Para los problemas de agrupamiento métrico bien estudiados de k -medianas y k -medias parametrizados por el número k de centros, se sabe que no(1+2/mi−ε){\displaystyle (1+2/e-\varepsilon)}-aproximación para k-mediana y no(1+8/mi−ε){\displaystyle (1+8/e-\varepsilon)}-La aproximación para k-Means se puede calcular enF(k)norteO(1){\displaystyle f(k)n^{O(1)}}tiempo para cualquier función f , bajo Gap- ETH . [ 15 ] Existen algoritmos de aproximación parametrizados coincidentes, [ 15 ] pero no se sabe si las aproximaciones coincidentes se pueden calcular en tiempo polinomial.

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

k -Centro

Para el problema del k -centro métrico se puede calcular una aproximación 2 en tiempo polinomial. Sin embargo, al parametrizar por el número k de centros, [ 22 ] la dimensión de duplicación (de hecho, la dimensión de una métrica de Manhattan ), [ 23 ] o la dimensión de la autopista , [ 22 ] no hay parametrizado(2−ε){\displaystyle (2-\varepsilon )}Existe un algoritmo de aproximación, bajo supuestos de complejidad estándar . Además, el problema k-Center es W[1]-difícil 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 autopista y el ancho de camino . [ 24 ] Sin embargo, cuando se combina k con la dimensión de duplicación existe un EPAS, [ 24 ] y lo mismo ocurre cuando se combina k con la dimensión de autopista . [ 25 ] 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 autopista como parámetro. [ 26 ] Con respecto al ancho de camino, 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 . [ 27 ]

Subgrafo más denso

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 biario ), donde la tarea es encontrar un subgrafo con k vértices con el número máximo de aristas. No es difícil obtener un(k−1){\displaystyle (k-1)}-aproximación simplemente eligiendo un tamaño que coincidak/2{\displaystyle k/2}en el grafo de entrada dado, ya que el número máximo de aristas en k vértices siempre es como máximo(k2)=k(k−1)/2{\displaystyle {k \choose 2}=k(k-1)/2}. Esto también es asintóticamente óptimo, ya que bajo Gap- ETH nok1−o(1){\displaystyle k^{1-o(1)}}La aproximación se puede calcular en tiempo FPT parametrizado por k . [ 28 ]

Conjunto dominante

Para el problema del conjunto dominante es W[1]-difícil calcular cualquiergramo(k){\displaystyle g(k)}-aproximación enF(k)norteO(1){\displaystyle f(k)n^{O(1)}}tiempo para cualesquiera funciones g y f . [ 29 ]

Kernelización aproximada

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

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 demostración de este hecho es muy similar a la de los núcleos regulares . [ 30 ] Sin embargo, el núcleo aproximado garantizado podría tener un tamaño exponencial (o peor) en el parámetro de entrada. Por lo tanto, resulta 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 en1+ε{\displaystyle 1+\varepsilon }para cualquierε>0{\displaystyle \varepsilon >0}.

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

Charlas sobre aproximaciones parametrizadas

  • Daniel Lokshtanov: Un esquema de aproximación parametrizado para el corte k-mínimo
  • Tuukka Korhonen: Algoritmo de aproximación 2 de tiempo exponencial único para el ancho de árbol
  • Karthik CS: Resultados recientes sobre la dificultad de la aproximación en la complejidad parametrizada
  • Ariel Kulik. Relaciones de recurrencia de dos variables con aplicación a aproximaciones parametrizadas.
  • Meirav Zehavi. Aproximación 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 de kernelización aproximada para redes de Steiner.

Referencias

  1. ↑ Marx, Daniel (2008). "Complejidad parametrizada y algoritmos de aproximación" . The Computer Journal . 51 (1): 60– 78. doi : 10.1093/comjnl/bxm048 .
  2. ↑ Feldmann, Andreas Emil; Karthik C. S; Lee, Euiwoong; Manurangsi, Pasin (2020). "Una revisión sobre la aproximación en la complejidad parametrizada: dificultad y algoritmos" . Algorithms . 13 (6): 146. arXiv : 2006.04411 . doi : 10.3390/a13060146 . ISSN 1999-4893 .  Este artículo incorpora texto de esta fuente, que está disponible bajo la licencia CC BY 4.0 .
  3. ↑ Manurangsi, Pasin (2018). "Inaproximabilidad de problemas de biclique máximo, k-corte mínimo y subgrafo denso de al menos k subgrafos a partir de la hipótesis de expansión de conjuntos pequeños" . Algorithms . 11 (1): 10. arXiv : 1705.03581 . doi : 10.3390/a11010010 . ISSN 1999-4893 . 
  4. ↑ G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael; Prieto, Elena ; Rosamund, Frances A. (1 de abril de 2003). "Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems" . Electronic Notes in Theoretical Computer Science . CATS'03, Computing: the Australasian Theory Symposium. 78 : 209–222 . doi : 10.1016/S1571-0661(04)81014-4 . hdl : 10230/36518 . ISSN 1571-0661 . 
  5. ↑ Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (25 de abril de 2022). "Un esquema de aproximación parametrizado para Min $k$-Cut" . SIAM Journal on Computing : FOCS20–205. arXiv : 2005.00134 . doi : 10.1137/20M1383197 . ISSN 0097-5397 . 
  6. ↑ Emil Feldmann, Andreas; Filtser, Arnold (enero de 2025), "Highway Dimension: a Metric View" , Actas del Simposio Anual ACM-SIAM de 2025 sobre Algoritmos Discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 3267–3276 , doi : 10.1137/1.9781611978322.104 , consultado el 2 de junio de 2025. 
  7. ↑ Dreyfus, SE; Wagner, RA (1971). "El problema de Steiner en grafos" . Networks . 1 (3): 195– 207. doi : 10.1002/net.3230010302 .
  8. ↑ Chlebík, Miroslav; Chlebíková, Janka (31 de octubre de 2008). "El problema del árbol de Steiner en gráficos: resultados de inaproximabilidad" . Informática Teórica . Aspectos algorítmicos de la informática global. 406 (3): 207– 214. doi : 10.1016/j.tcs.2008.06.046 . ISSN 0304-3975 . 
  9. 1 2 Dvořák, Pavel; Feldmann, Andreas E.; Knop, Dušan; Masařík, Tomáš; Toufar, Tomaš; Veselý, Pavel (1 de enero de 2021). "Esquemas de aproximación parametrizada para árboles Steiner con un pequeño número de vértices Steiner" . Revista SIAM de Matemática Discreta . 35 (1): 546– 574. arXiv : 1710.00668 . doi : 10.1137/18M1209489 . ISSN 0895-4801 . S2CID 3581913 .  
  10. ↑ Feldmann, Andreas Emil; Lampis, Michael (2024). "Algoritmos parametrizados para Steiner Forest en gráficos de ancho acotado". En Bringmann, Karl; Grohe, Martín; Puppis, Gabriele; Svensson, Ola (eds.). 51.º Coloquio internacional sobre autómatas, lenguajes y programación, ICALP 2024, 8 al 12 de julio de 2024, Tallin, Estonia . LÍPICOS. vol. 297. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 61:1–61:20. arXiv : 2402.09835 . doi : 10.4230/LIPICS.ICALP.2024.61 .  
  11. ↑ Guo, Jiong; Niedermeier, Rolf; Suchý, Ondřej (1 de enero de 2011). "Complejidad parametrizada de problemas de Steiner dirigidos ponderados por arcos" . SIAM Journal on Discrete Mathematics . 25 (2): 583– 599. doi : 10.1137/100794560 . ISSN 0895-4801 . 
  12. ↑ Halperin, Eran; Krauthgamer, Robert (9 de junio de 2003). «Inaproximabilidad polilogarítmica» . Actas del trigésimo quinto simposio anual de la ACM sobre Teoría de la Computación . STOC '03. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 585–594 . doi : 10.1145/780542.780628 . ISBN  978-1-58113-674-6. S2CID 8554166 . 
  13. ↑ Chitnis, Rajesh; Hajiaghayi, MohammadTaghi; Kortsarz, Guy (2013). "Algoritmos de aproximación y de parámetros fijos: una nueva perspectiva". En Gutin, Gregory; Szeider, Stefan (eds.). Computación parametrizada y exacta . Lecture Notes in Computer Science. Vol. 8246. Cham: Springer International Publishing. pp. 110–122 . arXiv : 1308.3520 . doi : 10.1007/978-3-319-03898-8_11 . ISBN   978-3-319-03898-8. S2CID 6796132 . 
  14. ↑ Chitnis, Rajesh; Feldmann, Andreas Emil; Manurangsi, Pasin (19 de abril de 2021). "Algoritmos de aproximación parametrizados para problemas de redes de Steiner bidireccionales" . ACM Transactions on Algorithms . 17 (2): 12:1–12:68. arXiv : 1707.06499 . doi : 10.1145/3447584 . ISSN 1549-6325 . S2CID 235372580 .  
  15. 1 2 Cohen-Addad, Vincent; Gupta, Anupam; Kumar, Amit; Lee, Euiwoong; Li, Jason (2019). Baier, Christel; Chatzigiannakis, Ioannis; Flocchini, Paola; Leonardi, Stefano (eds.). "Aproximaciones FPT ajustadas para k-mediana y k-media" . 46.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2019) . Actas Internacionales Leibniz en Informática (LIPIcs). 132. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 42:1–42:14. doi : 10.4230/LIPIcs.ICALP.2019.42 . ISBN 978-3-95977-109-2. S2CID 139103417 . 
  16. ↑ Kolliopoulos, Stavros G.; Rao, Satish (1999). "Un esquema de aproximación casi lineal para el problema de la k-mediana euclidiana". En Nešetřil, Jaroslav (ed.). Algoritmos - ESA' 99. Notas de clase en informática. Vol. 1643. Berlín, Heidelberg: Springer Berlin Heidelberg. pp. 378–389 . doi : 10.1007/3-540-48481-7_33 . ISBN   978-3-540-66251-8.
  17. ↑ Cohen-Addad, Vincent (2018). "Un esquema de aproximación rápida para k-medias de baja dimensión". Actas del Simposio Anual ACM-SIAM de 2018 sobre Algoritmos Discretos (SODA) . Actas. Sociedad de Matemáticas Industriales y Aplicadas. págs. 430–440 . arXiv : 1708.07381 . doi : 10.1137/1.9781611975031.29 . ISBN  978-1-61197-503-1. S2CID 30474859 . 
  18. ↑ Feldman, Dan; Monemizadeh, Morteza; Sohler, Christian (6 de junio de 2007). «Un PTAS para agrupamiento k-means basado en conjuntos centrales débiles» . Actas del vigésimo tercer simposio anual sobre geometría computacional - SCG '07 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 11-18 . doi : 10.1145/1247069.1247072 . ISBN  978-1-59593-705-6. S2CID 5694112 . 
  19. ↑ Feldman, Dan; Langberg, Michael (6 de junio de 2011). «Un marco unificado para la aproximación y agrupación de datos» . Actas del cuadragésimo tercer simposio anual de la ACM sobre Teoría de la Computación . STOC '11. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 569–578 . doi : 10.1145/1993636.1993712 . ISBN  978-1-4503-0691-1. S2CID 2677556 . 
  20. ↑ Cohen-Addad, Vincent; Feldmann, Andreas Emil; Saulpic, David (31 de octubre de 2021). "Esquemas de aproximación temporal casi lineal para la agrupación en métricas de duplicación" . Journal of the ACM . 68 (6): 44:1–44:34. arXiv : 1812.08664 . doi : 10.1145/3477541 . ISSN 0004-5411 . S2CID 240476191 .  
  21. ↑ Feldmann, Andreas Emil; Saulpic, David (1 de diciembre de 2021). "Esquemas de aproximación en tiempo polinomial para la agrupación en grafos de baja dimensión de autopista" . Journal of Computer and System Sciences . 122 : 72–93 . doi : 10.1016/j.jcss.2021.06.002 . ISSN 0022-0000 . 
  22. 1 2 Feldmann, Andreas Emil (1 de marzo de 2019). "Aproximaciones de parámetros fijos para problemas de k-centro en grafos de baja dimensión de autopista" . Algorithmica . 81 (3): 1031– 1052. arXiv : 1605.02530 . doi : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .  
  23. ↑ Feder, Tomás; Greene, Daniel (1 de enero de 1988). «Algoritmos óptimos para la agrupación aproximada» . Actas del vigésimo simposio anual de la ACM sobre Teoría de la Computación - STOC '88 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 434–444 . doi : 10.1145/62212.62255 . ISBN  978-0-89791-264-8. S2CID 658151 . 
  24. 1 2 Feldmann, Andreas Emil; Marx, Dániel (1 de julio de 2020). "La dificultad parametrizada del problema del k-centro en redes de transporte" . Algorithmica . 82 (7): 1989– 2005. arXiv : 1802.08563 . doi : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .  
  25. ↑ Becker, Amariah; Klein, Philip N.; Saulpic, David (2018). Azar, Yossi; Bast, Hannah; Herman, Grzegorz (eds.). "Esquemas de aproximación en tiempo polinomial para el enrutamiento de vehículos con k-centro, k-mediana y capacidad limitada en dimensiones de autopistas acotadas" . 26.º Simposio Europeo Anual sobre Algoritmos (ESA 2018) . Actas Internacionales Leibniz en Informática (LIPIcs). 112. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 8:1–8:15. doi : 10.4230/LIPIcs.ESA.2018.8 . ISBN 978-3-95977-081-1.
  26. ↑ Feldmann, Andreas Emil; Vu, Tung Anh (2022). " K -Centro generalizado : Distinción entre duplicación y dimensión de autopista". En Bekos, Michael A.; Kaufmann, Michael (eds.). Conceptos de teoría de grafos en informática . Lecture Notes in Computer Science. Vol. 13453. Cham: Springer International Publishing. pp. 215–229 . arXiv : 2209.00675 . doi : 10.1007/978-3-031-15914-5_16 . ISBN   978-3-031-15914-5.
  27. ↑ Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis Th. (15 de julio de 2019). "Parámetros estructurales, límites ajustados y aproximación para el centro (k,r)" . Matemáticas Aplicadas Discretas . Optimización Combinatoria: entre la Práctica y la Teoría. 264 : 90–117 . arXiv : 1704.08868 . doi : 10.1016/j.dam.2018.11.002 . ISSN 0166-218X . 
  28. ↑ Dinur, Irit; Manurangsi, Pasin (2018). Karlin, Anna R. (ed.). "ETH-Dardness of Approximating 2-CSPs and Directed Steiner Network" . 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) . Leibniz International Proceedings in Informatics (LIPIcs). 94. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 36:1–36:20. doi : 10.4230/LIPIcs.ITCS.2018.36 . ISBN 978-3-95977-060-6. S2CID 4681120 . 
  29. ↑ S., Karthik C.; Laekhanukit, Bundit; Manurangsi, Pasin (20 de junio de 2018). "Sobre la complejidad parametrizada de la aproximación del conjunto dominante" . Actas del 50.º Simposio Anual ACM SIGACT sobre Teoría de la Computación . STOC 2018. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1283–1296 . arXiv : 1711.11029 . doi : 10.1145 /3188745.3188896 . ISBN  978-1-4503-5559-9. S2CID 3170316 . 
  30. 1 2 3 4 Lokshtanov, Daniel; Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (19 de junio de 2017). "Lossy kernelization" . Actas del 49.º Simposio Anual ACM SIGACT sobre Teoría de la Computación (PDF) . STOC 2017. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 224–237 . doi : 10.1145/3055399.3055456 . ISBN  978-1-4503-4528-6. S2CID 14599219 . 
  31. ^ Hermelín, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi (1 de marzo de 2015). "Una teoría de la completitud para la kernelización polinómica (Turing)" . Algorítmica . 71 (3): 702– 730. doi : 10.1007/s00453-014-9910-8 . ISSN 1432-0541 . S2CID 253973283 .  
  32. ↑ Fellows, Michael R.; Kulik, Ariel; Rosamond, Frances; Shachnai, Hadas (1 de mayo de 2018). "Aproximación parametrizada mediante transformaciones que preservan la fidelidad" . Journal of Computer and System Sciences . 93 : 30–40 . doi : 10.1016/j.jcss.2017.11.001 . ISSN 0022-0000 .