Matriz Monge

En matemáticas aplicadas a la informática , las matrices de Monge son objetos matemáticos que reciben su nombre de su descubridor, el matemático francés Gaspard Monge .

Se dice que una matriz m x n es una matriz de Monge si, para todo${\displaystyle i,j,k,\ell }$de tal manera que $${\displaystyle 1\leq i<k\leq m{\text{ y }}1\leq j<\ell \leq n,}$$ se obtiene ^{[ 1 ]}$${\displaystyle A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].}$$ En otras palabras, para cualesquiera dos filas y dos columnas de una matriz de Monge, los cuatro elementos en los puntos de intersección (una submatriz de 2 × 2) tienen la propiedad de que la suma de los elementos superior izquierdo e inferior derecho (en la diagonal principal ) es menor o igual que la suma de los elementos inferior izquierdo y superior derecho (en la antidiagonal ).  

Esta matriz es un arreglo de Monge:

${\displaystyle {\begin{bmatrix}10&17&13&28&23\\17&22&16&29&23\\24&28&22&34&24\\11&13&6&17&7\\45&44&32&37&23\\36&33&19&21&6\\75&66&51&53&34\end{bmatrix}}}$

Por ejemplo, tomemos la intersección de las filas 2 y 4 con las columnas 1 y 5. Los cuatro elementos son: $${\displaystyle {\begin{bmatrix}17&23\\11&7\end{bmatrix}}.}$$ La suma de los elementos superior izquierdo e inferior derecho (17 + 7 = 24) no es mayor que la suma de los elementos inferior izquierdo y superior derecho (23 + 11 = 34).

• La definición anterior es equivalente a la afirmación

Una matriz es un arreglo de Monge si y solo si${\displaystyle A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]}$a pesar de${\displaystyle 1\leq i<m}$y${\displaystyle 1\leq j<n}$. ^{[ 1 ]}

• Cualquier submatriz producida al seleccionar ciertas filas y columnas de una matriz Monge original será, a su vez, una matriz Monge.
• Cualquier combinación lineal con coeficientes no negativos de matrices de Monge es, a su vez, una matriz de Monge.
• Cada matriz de Monge es totalmente monótona, lo que significa que sus mínimos de fila ocurren en una secuencia no decreciente de columnas, y que la misma propiedad es cierta para cada submatriz. Esta propiedad permite encontrar rápidamente los mínimos de fila utilizando el algoritmo SMAWK . Si marcas con un círculo el mínimo más a la izquierda de cada fila, descubrirás que tus círculos se desplazan hacia abajo a la derecha; es decir, si${\displaystyle f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]}$, entonces${\displaystyle f(j)\leq f(j+1)}$a pesar de${\displaystyle 1\leq j<n}$De forma simétrica, si se marca el mínimo superior de cada columna, los círculos avanzarán hacia la derecha y hacia abajo. Los máximos de fila y columna avanzarán en la dirección opuesta: hacia arriba a la derecha y hacia abajo a la izquierda.
• Se ha propuesto la noción de arreglos de Monge débiles ; un arreglo de Monge débil es una matriz cuadrada de n × n que satisface la propiedad de Monge.${\displaystyle A[i,i]+A[r,s]\leq A[i,s]+A[r,i]}$solo para todos${\displaystyle 1\leq i<r,s\leq n}$.
• La matriz de Monge es simplemente otro nombre para la función submodular de dos variables discretas. Precisamente, A es una matriz de Monge si y solo si A [ i , j ] es una función submodular de las variables i y j . 

Las matrices de Monge tienen aplicaciones en problemas de optimización combinatoria :

• Cuando el problema del viajante tiene una matriz de costos que es una matriz de Monge, se puede resolver en tiempo cuadrático. ^{[ 1 ] [ 2 ]}
• Una matriz de Monge cuadrada que además es simétrica respecto a su diagonal principal se denomina matriz de Supnick (en honor a Fred Supnick ). Cualquier combinación lineal de matrices de Supnick es, a su vez, una matriz de Supnick ^{[ 1 ]} , y cuando la matriz de costos en un problema del viajante es de Supnick, la solución óptima es una ruta predeterminada, que no se ve afectada por los valores específicos dentro de la matriz ^{[ 2 ] .}

• Deineko, Vladimir G.; Woeginger, Gerhard J. (octubre de 2006). "Algunos problemas relacionados con vendedores ambulantes, dianas de dardos y monedas de euro" (PDF) . Boletín de la Asociación Europea de Ciencias de la Computación Teórica . 90. EATCS : 43–52 . ISSN 0252-9742 .