He estado luchando con un problema combinatorio que eventualmente se traduce en lo siguiente:
Dado un $n \times n$ matriz no negativa, encontrar una permutación de las filas que maximice el rastro.
Podría computar todos $n!$ permutaciones y encontrar la que maximiza el rastro, pero que no es computablemente eficiente. ¿Cuál es la forma más eficiente de lograrlo?
Si ayuda, esto es lo mismo que encontrar $n$ entradas de la matriz sin que haya dos de ellas en la misma fila o columna, de modo que la suma de estas entradas es máxima.
2 votos
Una solución codiciosa: encontrar $(i_1,j_1)=\operatorname{arg\,max} A_{ij}$ , entonces para cada uno de los restantes $k=2,\ldots,n$ , $(i_k,j_k)=\operatorname{arg\,max} A_{ij}$ en $i\not\in\{i_1,\ldots,i_{k-1}\}$ y $j\not\in \{j_1,\ldots,j_{k-1}\}$ . Ahora permuta $A$ para que la fila $i_k \to j_k$ se traslada a $j_k$ . Sospecho que esto es óptimo pero no lo he probado. La complejidad computacional es $n^2 + (n-1)^2 + \dots + 1^2 = \tfrac{1}{6}n(n+1)(2n+1) = \mathcal{O}(n^3)$
2 votos
Solución no golosa: Este problema es $\operatorname{maximize} \text{tr}(P A)$ sobre matrices de permutación $P$ . Esto no es convexo, pero podemos calcular un límite superior (que podría ser potencialmente muy bueno o correcto) maximizando el mismo $\operatorname{maximize} \text{tr}(P A)$ sobre el casco convexo del conjunto de matrices de permutación, el politopo de Birkhoff el conjunto de matrices doblemente estocásticas. En teoría, se trata de un programa lineal que puede resolverse en tiempo polinómico $\mathcal{O}(n^3)$ tiempo al representar bien la restricción.
3 votos
La solución codiciosa no da la mejor respuesta. He aquí un ejemplo de por qué: $A = [3, 5; 0, 3]$ .
0 votos
La solución no codiciosa parece interesante. ¿Hay algo que garantice que el máximo se produzca en las esquinas?
0 votos
No estoy seguro; pensaré en ello mañana si encuentro tiempo. Buena captura con el contraejemplo codicioso. Me pregunto si la aproximación es arbitrariamente mala, y si no, cuál es el ratio de aproximación.
1 votos
¡Oh! En realidad creo que sabemos que el objetivo se maximiza en las esquinas precisamente porque el objetivo es lineal, y los programas lineales siempre tienen un máximo en los vértices (¡utiliza el algoritmo simplex, por ejemplo)! Así que la solución no codiciosa funcionaría. Supongo que mañana escribiré una respuesta :)
1 votos
@Keivan Sobre el uso de LP, echa un vistazo a este .
1 votos
@cdipaolo El mínimo también se puede alcanzar en una faceta.
0 votos
@RodrigodeAzevedo tienes razón por supuesto, pero siempre podemos encontrar un maximizador en un vértice para que no afecte a nuestro problema.
0 votos
La solución codiciosa de cdipaolo puede no encontrar siempre el óptimo global, pero después de una pequeña prueba de cocina encuentro que está consistentemente (bien) en el percentil 99 (del espacio de soluciones de tamaño n!) al menos para n<=10.