¿Este problema de optimización combinatoria es NP-hard?

Question

Estoy trabajando en un problema de optimización combinatoria que sospecho que es NP-hard, y un algoritmo genético ha funcionado bien con nuestro conjunto de datos. Somos un grupo de investigación y planeamos publicar nuestros resultados en nuestro campo (no en matemáticas o CS), y me gustaría explorar la pregunta NP-difícil antes de enviar el manuscrito para su revisión.

Hay dos cuestiones principales:

1) que me gustaría saber si este problema de optimización particular, se ha estudiado. He buscado intensamente la luz pero no he visto nada exactamente igual.

2) Si el problema no se ha estudiado, podría tomar algunas medidas para hacer una prueba de reducibilidad, y me gustaría obtener algunos consejos para obtener buenos candidatos NP-completos para la reducción.

El problema se puede describir de dos maneras, como una variante de subsecuencia, y como un problema de gráfico bipartito.

En el sabor posterior, quiero encontrar una subsecuencia "relajada" que permita permutaciones, y optimizar para minimizar el conteo de permutación. Por ejemplo: (= cualquier otra Char.)

Consulta: abc, Target: ..babc, resultado: abc (subsecuencia normal)

Consulta: abc, Target: ..baca, resultado: bac (subsecuencia con una permutación)

La formulación bipartita es un problema coincidente o un problema de asignación lineal, con el gráfico dividido en nodos de caracteres de consulta y nodos de caracteres de destino. Los bordes conectan los caracteres de consulta con los caracteres de destino, de modo que hay exactamente un borde desde cada char de consulta hasta un char objetivo. La función objetivo es minimizar el número de cruces de borde (también llamado "número de cruce" en el encendido). Esto es similar a los algoritmos de diseño de gráficos bipartitos que reordenan la colocación de nodos para minimizar los cruces de borde, pero mi problema requiere que ambos órdenes de nodo permanezcan fijos.

¿Algún comentario de los expertos sobre las preguntas 1 o 2?

¡Gracias de antemano!

Answer 1

Solo una idea: ¿Es de alguna manera equivalente a encontrar el número mínimo de intercambio necesario para ordenar una matriz (MIN-SBR)? Si es así, esto es NP-Hard.

(por cierto, estás trabajando en algo similar to this?)

Answer 2

El problema con el "problema de la palabra" debería ser más difícil, ¿verdad? - J-16 SDiZ 14

Sí, tener varias ocurrencias de carbonilla en el objetivo parece hacer mi problema más difícil que MIN-SBR, por lo que desde ese ángulo mi problema sería al menos tan difícil como NP-completo. Por otro lado, todavía no tengo claro cómo su noción central de reversiones de bloque afectaría mi afirmación de NP-completitud.

Estoy seguro de que me gustaría saber si mi optimización puede resolverse en tiempo polinomial. Dicho de otra manera, sería embarazoso si un revisor volviera con cinco líneas de pseudocódigo que encuentran el máximo global en O (n).

Answer 3

Para piccolbo:

Si no está publicando en matemáticas o CS, un resultado NP-completitud será irrelevante y solo irritar el biólogo o MD haciendo la revisión. Estado allí.

Usted apuesta. El informe principal será sobre los resultados húmedos, pero podríamos elegir una revista que sea más interdisciplinaria. Además, querer saber sobre la NP-ness es en parte para mi propia edificación. Sería bastante inapropiado usar un algoritmo genético si no está justificado, y si hay una manera de encontrar el máximo global garantizado en tiempo polinomial. En este momento, la AG está encontrando buenas soluciones, pero obviamente es difícil saber si está buscando la mejor solución.

¿Cuál es su significado de permutación? ¿Una que involucra solo dos caracteres? ¿O solo dos adyacentes? Una permutación que creo que en su significado general le permite reorganizar toda la cadena, pero entonces el problema se vuelve trivial.

Es una cantidad arbitraria de permutaciones en la cadena de destino, y la minimización del número de permutaciones (es decir, cruces de borde en la formulación bipartita) es la función objetivo. Las permutaciones pueden estar en cualquier lugar y se distribuyen de forma independiente, por lo que la adyacencia ocurriría (con poca frecuencia) por casualidad. El orden de las cadenas de consulta y destino es fijo, por lo que no puedo hacer ninguna reorganización.

Si pruebo que es NP-hard, ¿obtengo la coautoría?

Veamos la prueba :-)

Answer 4

haría, consulta: abc Objetivo: ..c.b.a.a Resultado: cba, sea tres permutaciones (como por su uso de la expresión), entonces? Si es así, entonces tal vez te refieres a transposiciones en lugar de permutaciones. Una transposición es el intercambio de dos caracteres adyacentes.

Buena pregunta. Estamos interesados ​​en un mapeo desde Query -> Target que tenga como pocos cruces como sea posible. Esta es en gran medida la motivación para mencionar los cruces de borde bipartito en la publicación original. Alternativamente, puede pensar en maximizar una estadística de rango, como Rho de Spearman, sobre el mapeo.

También, por curiosidad, ¿cuántos caracteres únicos hay en la consulta/destino? - Justin Peel 18

Consulta típica: 100, objetivo típico: 1000. Combinatorialmente, es un espacio de gran solución.

Answer 5

No creo que esto sea NP-hard. Vea el trabajo de Pevzner y Hannehali. Un documento que viene a la mente se titula `From Cabbage to Turnip ''. La idea es encontrar el número mínimo de inversiones para ir de una cadena a otra. Tienen un algoritmo de poliettime para esto.