¿Existe una manera de resolver eficientemente (tal vez aproximadamente) $\left\|A-XBX^T\right\|_F\xrightarrow[X]{}\min$ donde X es una matriz de permutación y A, B son matrices reales cuadradas densas y simétricas?
Respuesta
¿Demasiados anuncios?
Un algoritmo para este problema podría usarse para resolver el problema de isomorfismo del grafo: dejemos $B_{i,j}$ sea 0 o 1 dependiendo de si el borde $(i,j)$ está en el gráfico $B$ y que $A_{i,j}$ sea 0 o 1 dependiendo de si el borde $(i,j)$ está en el gráfico $A$ . Los dos gráficos son isomorfos si y sólo si existe una solución a su problema con norma de Frobenius 0.
Es cierto que ese isomorfismo de grafos es resoluble en tiempo cuasi-polinómico, pero ese algoritmo tiene más interés teórico que práctico.
Su problema es más general que el problema de isomorfismo de grafos, por lo que esperaría que fuera difícil en la práctica para instancias grandes. Si tuviera que resolverlo exactamente para instancias pequeñas, probablemente intentaría desarrollar un algoritmo de rama y límite. Intentaría una heurística de búsqueda local para instancias más grandes.
