Encontrar una matriz de adyacencia simétrica más cercana a una matriz de adyacencia dada (no simétrica)

Question

Estoy tratando de resolver un problema en los gráficos, que he reducido el siguiente problema de optimización en la matriz $X \in \{0,1\}^{n \times n}$

$$\begin{array}{ll} \text{minimize} & \| X - A \|_F^2\\ \text{subject to} & X 1_n = m 1_n\\ & X=X^\top\end{array}$$

donde la matriz de $A \in \{0,1\}^{n \times n}$ es dado. Matriz $X$ es la matriz de adyacencia de un no-dirigidos $m$-gráfico regular, mientras que la matriz $A$ es la matriz de adyacencia de un grafo dirigido.

Yo soy bastante ignorante sobre cómo ir sobre la solución de este problema y sería feliz de llegar a una dirección.

Answer 1

Tenemos el siguiente problema de optimización en la matriz $\mathrm X \in \{0,1\}^{n \times n}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm X - \mathrm A \|_{\text{F}}^2\\ \text{subject to} & \mathrm X 1_n = m 1_n\\ & \mathrm X = \mathrm X^\top\\ & \mathrm X \in \{0,1\}^{n \times n}\end{array}$$

donde la matriz de $\mathrm A \in \{0,1\}^{n \times n}$ es dado. Tenga en cuenta que

$$\| \mathrm X - \mathrm A \|_{\text{F}}^2 = \| \mathrm X \|_{\text{F}}^2 - 2 \langle \mathrm A, \mathrm X \rangle + \| \mathrm A \|_{\text{F}}^2$$

y que $\| \mathrm X \|_{\text{F}}^2 = m n$, debido a las restricciones. Por lo tanto, tenemos el siguiente programa entero (IP)

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A, \mathrm X \rangle\\ \text{subject to} & \mathrm X 1_n = m 1_n\\ & \mathrm X = \mathrm X^\top\\ & \mathrm X \in \{0,1\}^{n \times n}\end{array}$$

lo que parece ser una generalización del problema de la asignación. Tal vez no es una generalización del algoritmo húngaro, también.