Hispanopedia WikiLa intermediación es un problema algorítmico en la teoría del orden que trata de ordenar una colección de elementos sujetos a restricciones que establecen que algunos elementos deben colocarse entre otros. [1] Tiene aplicaciones en bioinformática [2] y Opatrný (1979) demostró que es NP-completo . [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 se requiere que los elementos de cada triple sean consecutivos en la salida. [1] [3]
Ejemplos
A modo de ejemplo, la colección de triples de entrada
- (2,1,3), (3,4,5), (1,4,5), (2,4,1), (5,2,3)
se satisface con el orden de salida
- 3, 1, 4, 2, 5
pero no por
- 3, 1, 2, 4, 5.
En el primero de estos ordenamientos 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 ordenamiento 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 tripletas 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 tripletas sin solución válida, que no contengan ese par de tripletas contradictorias.
Complejidad
Opatrný (1979) mostró 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-completa de dos maneras, por una reducción de 3-satisfacibilidad y también por una reducción diferente de 2-coloración del hipergrafo . [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 que sea el inicio del ordenamiento y luego usando los triples que involucran a 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 razó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 instancias densas 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 aleatoriamente, y esta estrategia simple da la mejor aproximación posible en tiempo polinomial si la conjetura de juegos únicos es verdadera. [6] También es posible usar programación semidefinida o métodos combinatorios para encontrar un ordenamiento que satisfaga al menos la mitad de los triples de cualquier instancia satisfacible, 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 es manejable 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 la calidad | C |/3 garantizada en expectativa por un ordenamiento aleatorio. [8]
Aunque no está garantizado 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 del problema de la intermediación surge en la bioinformática , como parte del proceso de mapeo genético . Ciertos tipos de experimentos genéticos pueden utilizarse para determinar el orden de los triples de marcadores genéticos, pero no distinguen una secuencia genética de su reversión, por lo que la información obtenida de dicho experimento determina únicamente cuál de los tres marcadores es el del medio. El problema de la intermediación es una abstracción del problema de ensamblar una colección de marcadores en una sola secuencia dados los datos experimentales de este tipo. [1] [2]
El problema de intermediación también se ha utilizado para modelar teorías de probabilidad , causalidad y tiempo . [9]
Referencias
- ^ abcde Chor, Benny ; Sudan, 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.
- ^ abc Slonim, Donna; Kruglyak, Leonid; Stein, Lincoln; Lander, Eric (1997), "Construcció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.
- ^ abc Opatrný, J. (1979), "Problema de ordenamiento total", 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. APPROX 2011, RANDOM 2011 , Lecture Notes in Computer Science , vol. 6845, págs. 277–288, arXiv : 0911.2214 , doi :10.1007/978-3-642-22935-0_24, ISBN 978-3-642-22934-3, Número de identificación del sujeto 7180847
- ^ Charikar, Moses ; Guruswami, Venkatesan ; Manokaran, Rajsekar (2009), "Cada CSP de permutación de aridad 3 es resistente a la aproximación", 24.ª Conferencia Anual IEEE sobre Complejidad Computacional , págs. 62-73, doi :10.1109/CCC.2009.29, ISBN 978-0-7695-3717-7, MR 2932455, S2CID 257225.
- ^ Makarychev, Yury (2012), "Algoritmo de aproximación de tiempo lineal simple para intermediación", Operations Research Letters , 40 (6): 450–452, doi :10.1016/j.orl.2012.08.008, MR 2998680.
- ^ Gutin, Gregory ; Kim, Eun Jung ; Mnich, Matthias; Yeo, Anders (2010), "Intermediación parametrizada por encima de un límite inferior estricto", 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.