La intermediación es un problema algorítmico en la teoría de pedidos sobre ordenar una colección de elementos sujetos a restricciones que algunos elementos deben colocarse entre otros. [1] Tiene aplicaciones en bioinformática [2] y ha demostrado ser NP-completo por Opatrný (1979) . [3]
Planteamiento del problema
La entrada a un problema de intermediación es una colección de triples ordenados de elementos. Los elementos enumerados en estos triples deben colocarse en un orden total , con la propiedad de que para cada uno de los triples dados, el elemento del medio en el triple aparece en la salida en algún lugar entre los otros dos elementos. No es necesario que los elementos de cada triple sean consecutivos en la salida. [1] [3]
Ejemplos de
Como ejemplo, la colección de entradas triplica
- (2,1,3), (3,4,5), (1,4,5), (2,4,1), (5,2,3)
está satisfecho con el pedido de salida
- 3, 1, 4, 2, 5
pero no por
- 3, 1, 2, 4, 5.
En el primero de estos pedidos de salida, para los cinco triples de entrada, el elemento del medio del triple aparece entre los otros dos elementos.Sin embargo, para el segundo orden de salida, el elemento 4 no está entre los elementos 1 y 2, lo que contradice el requisito dado. por el triple (2,4,1).
Si una entrada contiene dos triples como (1, 2, 3) y (2, 3, 1) con los mismos tres elementos pero una elección diferente del elemento del medio, entonces no hay una solución válida. Sin embargo, hay formas más complicadas de formar un conjunto de triples sin solución válida, que no contienen un par de triples tan contradictorios.
Complejidad
Opatrný (1979) demostró que la versión de decisión del problema de intermediación (en el que un algoritmo debe decidir si existe o no una solución válida) es NP-completo de dos maneras, por una reducción de 3-satisfacibilidad y también por una reducción diferente. de hypergraph 2-coloración . [3] Sin embargo, se puede resolver fácilmente cuando todos los triples desordenados de elementos están representados por un triple ordenado de la entrada, eligiendo uno de los dos elementos que no están entre otros para ser el inicio del pedido y luego usando el triples que involucran este elemento para comparar las posiciones relativas de cada par de elementos restantes.
El problema relacionado de encontrar un ordenamiento que maximice el número de triples satisfechos es MAXSNP-hard , lo que implica que es imposible lograr una relación de aproximación arbitrariamente cercana a 1 en tiempo polinomial a menos que P = NP . [1] Sigue siendo difícil de resolver o aproximar incluso para casos densos que incluyen un triple ordenado para cada posible triple desordenado de elementos. [4] Se demostró que la versión mínima del problema restringida a los torneos tenía esquemas de aproximación de tiempo polinomial (PTAS). [5] Se puede lograr una razón de aproximación de 1/3 (en expectativa) ordenando los elementos al azar, y esta estrategia simple da la mejor aproximación posible de tiempo polinomial si la conjetura de los juegos únicos es cierta. [6] También es posible usar programación semidefinida o métodos combinatorios para encontrar un orden que satisfaga al menos la mitad de los triples de cualquier instancia satisfactoria, en tiempo polinomial. [1] [7]
En la complejidad parametrizada , el problema de satisfacer tantas restricciones como sea posible a partir de un conjunto C de restricciones se puede tratar con parámetros fijos cuando se parametriza mediante la diferencia q - | C | / 3 entre la calidad de la solución q encontrada por el algoritmo parametrizado y el | Calidad C | / 3 garantizada a la expectativa mediante un pedido aleatorio. [8]
Aunque no se garantiza que tenga éxito, una heurística codiciosa puede encontrar soluciones a muchos casos del problema de intermediación que surgen en la práctica. [2]
Aplicaciones
Una aplicación de la intermediación surge en bioinformática , como parte del proceso de mapeo de genes . Ciertos tipos de experimentos genéticos pueden usarse para determinar el orden de los triples de los marcadores genéticos, pero no distinguen una secuencia genética de su inversión, por lo que la información obtenida de dicho experimento determina solo cuál de los tres marcadores es el del medio. El problema de la intermediación es una abstracción del problema de reunir una colección de marcadores en una sola secuencia dados los datos experimentales de este tipo. [1] [2]
El problema de la intermediación también se ha utilizado para modelar teorías de probabilidad , causalidad y tiempo . [9]
Referencias
- ^ a b c d e Chor, Benny; Sudán, Madhu (1998), "Un enfoque geométrico de la intermediación", SIAM Journal on Discrete Mathematics , 11 (4): 511–523 (electrónico), doi : 10.1137 / S0895480195296221 , MR 1640920.
- ^ a b c Slonim, Donna; Kruglyak, Leonid; Stein, Lincoln; Lander, Eric (1997), "Creación de mapas del genoma humano con híbridos de radiación", Journal of Computational Biology , 4 (4): 487–504, doi : 10.1089 / cmb.1997.4.487 , PMID 9385541.
- ^ a b c Opatrný, J. (1979), "Total ordering problem", SIAM Journal on Computing , 8 (1): 111-114, doi : 10.1137 / 0208008 , MR 0522973.
- ^ Ailon, Nir; Alon, Noga (2007), "Dureza de problemas completamente densos", Información y Computación , 205 (8): 1117–1129, doi : 10.1016 / j.ic.2007.02.006 , MR 2340896.
- ^ Karpinski, Marek; Schudy, Warren (2011), "Esquemas de aproximación para el problema de intermediación en torneos y problemas de clasificación relacionados", en LA Goldberg y K. Jansen y R.Ravi y JDP Rolim (ed.), Proc. APROX 2011, RANDOM 2011 , Lecture Notes in Computer Science , 6845 , págs. 277–288, arXiv : 0911.2214 , doi : 10.1007 / 978-3-642-22935-0_24 , S2CID 7180847
- ^ Charikar, Moisés ; Guruswami, Venkatesan ; Manokaran, Rajsekar (2009), "Cada CSP de permutación de arity 3 es resistente a la aproximación", 24a Conferencia Anual de IEEE sobre Complejidad Computacional , págs. 62–73, doi : 10.1109 / CCC.2009.29 , MR 2932455 , S2CID 257225.
- ^ Makarychev, Yury (2012), "Algoritmo de aproximación de tiempo lineal simple para la intermediación", Cartas de investigación de operaciones , 40 (6): 450–452, doi : 10.1016 / j.orl.2012.08.008 , MR 2998680.
- ^ Gutin, Gregory; Kim, Eun Jung; Mnich, Matthias; Yeo, Anders (2010), "Betweenness parametrizada por encima del límite inferior ajustado", Journal of Computer and System Sciences , 76 (8): 872–878, arXiv : 0907.5427 , doi : 10.1016 / j.jcss.2010.05.001 , MR 2722353 , S2CID 3408698.
- ^ Chvátal, Vašek ; Wu, Baoyindureng (2011), "Sobre la intermediación causal de Reichenbach", Erkenntnis , 76 (1): 41–48, arXiv : 0902.1763 , doi : 10.1007 / s10670-011-9321-z , S2CID 14123568.