Pregunta:
Dada una instancia TSP simétrica finita con $2n$ sitios, cuál es la complejidad y cuáles son los algoritmos para determinar dos conjuntos de sitios $A$ y $B$ Cada uno de ellos contiene $n$ para que
la diferencia de las sumas de pesos de las aristas en $A$ y de aristas en $B$ es mínimo
la suma de pesos de las aristas que conectan un sitio en $A$ con un sitio en $B$ ¿es mínimo?
Ambos problemas comparten muchas similitudes con el Problema de partición para los que existen algoritmos codiciosos eficientes, enfoques de programación dinámica y métodos exactos (ver enlace).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
