Matriz de Monge

Tipo de objeto matemático

En matemáticas aplicadas a la informática , las matrices Monge , o matrices 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 por n es una matriz Monge si, para todos los 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 cualesquiera dos filas y dos columnas 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 lo largo de la diagonal principal ) es menor o igual que la suma de los elementos inferior izquierdo y superior derecho (a lo largo de la antidiagonal ).

Esta matriz es una matriz 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, tome 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 afirmación

Una matriz es una matriz 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 submatriz producida al seleccionar ciertas filas y columnas de una matriz Monge original será en sí misma una matriz 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 verdadera 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 abajo a la derecha; es decir, si , entonces para todos los . Simétricamente, si marca el mínimo más alto de cada columna, sus círculos marcharán hacia la derecha y hacia abajo. Los máximos de fila y columna marchan en la dirección opuesta: hacia arriba a la derecha y hacia 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 el concepto de matrices Monge débiles ; una matriz Monge débil es una matriz cuadrada de n por n que satisface la propiedad Monge solo para todos los . ${\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 simplemente otro nombre para una 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 , 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 cuadrada de Monge que también es simétrica respecto de su diagonal principal se denomina 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 de comercio 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áticas Aplicadas Discretas . 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 del problema del viajante de comercio con buena solución: una encuesta". SIAM Review . 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 vendedores ambulantes, los tableros de dardos y las monedas de euro" (PDF) . Boletín de la Asociación Europea de Ciencias Informáticas Teóricas . 90. EATCS : 43–52. ISSN  0252-9742.