matriz monge

Tipo de objeto matemático

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

Una matriz m -por- n se dice que es una matriz Monge si, para todo lo que ${\displaystyle \scriptstyle i,\,j,\,k,\,\ell }$

${\displaystyle 1\leq i<k\leq m{\text{ and }}1\leq j<\ell \leq n}$

se obtiene ^[1]

${\displaystyle A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].\,}$

Entonces, para dos filas y dos columnas cualesquiera de una matriz Monge (una submatriz de 2 × 2), los cuatro elementos en los puntos de intersección tienen la propiedad de que la suma de los elementos superior izquierdo e inferior derecho (a través de la diagonal principal ) es menor o igual a la suma de los elementos inferior izquierdo y superior derecho (a través de la antidiagonal ).

Esta matriz es una matriz 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}}}$

17 + 7 = 24

23 + 11 = 34

La suma de los elementos superior izquierdo e inferior derecho es menor o igual a la suma de los elementos inferior izquierdo y superior derecho.

Propiedades

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

Una matriz es una matriz de Monge si y sólo si para todos y . ^[1] ${\displaystyle A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]}$ ${\displaystyle 1\leq i<m}$ ${\displaystyle 1\leq j<n}$

• Cualquier subarreglo producido al seleccionar ciertas filas y columnas de un arreglo Monge original será en sí mismo un arreglo Monge.
• Cualquier combinación lineal con coeficientes no negativos de matrices Monge es en sí misma una matriz Monge.
• Cada matriz 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 marca con un círculo el mínimo más a la izquierda de cada fila, descubrirá que sus círculos marchan hacia la derecha; es decir, si , entonces para todos . Simétricamente, si marca el mínimo superior de cada columna, sus círculos marcharán hacia la derecha y hacia abajo. Los máximos de fila y columna marchan en dirección opuesta: arriba a la derecha y abajo a la izquierda. ${\displaystyle f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]}$ ${\displaystyle f(j)\leq f(j+1)}$ ${\displaystyle 1\leq j<n}$
• Se ha propuesto la noción de matrices Monge débiles ; una matriz de Monge débil es una matriz cuadrada de n por n que satisface la propiedad de Monge solo para todos . ${\displaystyle A[i,i]+A[r,s]\leq A[i,s]+A[r,i]}$ ${\displaystyle 1\leq i<r,s\leq n}$
• La matriz de Monge es solo otro nombre para la función submodular de dos variables discretas. Precisamente, A es una matriz de Monge si y sólo si A [ i , j ] es una función submodular de variables  i , j .

Aplicaciones

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 también es simétrica con respecto a su diagonal principal se llama matriz de Supnick (en honor a Fred Supnick). Cualquier combinación lineal de matrices de Supnick es en sí misma una matriz de Supnick, ^[1] y cuando la matriz de costos en un problema de viajante es Supnick, la solución óptima es una ruta predeterminada, que no se ve afectada por los valores específicos dentro de la matriz. ^[2]

Referencias

1. Burkard, Rainer E.; Klinz, Bettina; Rudolf, Rüdiger (1996). "Perspectivas de las propiedades de Monge en optimización". Matemática Aplicada Discreta . 70 (2). ELSEVIER: 95–96. doi :10.1016/0166-218x(95)00103-x.
2. Burkard, Rainer E.; Deineko, Vladimir G.; van Dal, René; van der Veen, Jack AA; Woeginger, Gerhard J. (1998). "Casos especiales bien solucionables del problema del viajante: una encuesta". Revisión SIAM . 40 (3): 496–546. doi :10.1137/S0036144596297514. ISSN  0036-1445.

• Deineko, Vladimir G.; Woeginger, Gerhard J. (octubre de 2006). "Algunos problemas relacionados con los viajantes de comercio, los dardos y las monedas de euro" (PDF) . Boletín de la Asociación Europea de Informática Teórica . 90 . EATC : 43–52. ISSN  0252-9742.