Tableau Monge - Monge array

En mathématiques appliquées à l' informatique , les tableaux de Monge , ou matrices de Monge , sont des objets mathématiques nommés en l'honneur de leur découvreur, le mathématicien français Gaspard Monge .

Une matrice m -by- n est dite un tableau de Monge si, pour tout tel ${\ displaystyle \ scriptstyle i, \, j, \, k, \, \ ell}$

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

on obtient

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

Ainsi, pour deux lignes et deux colonnes d'un tableau Monge (une sous-matrice 2 × 2), les quatre éléments aux points d'intersection ont la propriété que la somme des éléments supérieur gauche et inférieur droit (à travers la diagonale principale ) est inférieur ou égal à la somme des éléments inférieur gauche et supérieur droit (à travers l' antidiagonal ).

Cette matrice est un tableau 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}}}$

Par exemple, prenez l'intersection des lignes 2 et 4 avec les colonnes 1 et 5. Les quatre éléments sont:

${\ displaystyle {\ begin {bmatrix} 17 & 23 \\ 11 & 7 \ end {bmatrix}}}$

17 + 7 = 24

23 + 11 = 34

La somme des éléments supérieur gauche et inférieur droit est inférieure ou égale à la somme des éléments inférieur gauche et supérieur droit.

Propriétés

• La définition ci-dessus équivaut à la déclaration

Une matrice est un tableau Monge si et seulement si pour tout et .${\ 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}$

• Tout sous-tableau produit en sélectionnant certaines lignes et colonnes d'un tableau Monge d'origine sera lui-même un tableau Monge.
• Toute combinaison linéaire avec des coefficients non négatifs de tableaux Monge est elle-même un tableau Monge.
• Une propriété intéressante des tableaux Monge est que si vous marquez avec un cercle le minimum le plus à gauche de chaque ligne, vous découvrirez que vos cercles marchent vers le bas vers la droite; c'est-à-dire, si , alors pour tous . Symétriquement, si vous marquez le minimum supérieur de chaque colonne, vos cercles marcheront vers la droite et vers le bas. Les maxima de ligne et de colonne marchent dans la direction opposée: vers le haut vers la droite et vers le bas vers la gauche.${\ 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}$
• La notion de tableaux de Monge faibles a été proposée; un tableau de Monge faible est une matrice carrée n -by- n qui ne satisfait la propriété Monge que pour tous .${\ Displaystyle A [i, i] + A [r, s] \ leq A [i, s] + A [r, i]}$${\ displaystyle 1 \ leq i <r, s \ leq n}$
• Chaque tableau Monge est totalement monotone, ce qui signifie que ses minima de ligne se produisent dans une séquence non décroissante de colonnes et que la même propriété est vraie pour chaque sous-tableau. Cette propriété permet de trouver rapidement les minima de ligne à l'aide de l' algorithme SMAWK .
• La matrice de Monge est juste un autre nom pour la fonction sous-modulaire de deux variables discrètes. Précisément, A est une matrice de Monge si et seulement si A [ i , j ] est une fonction sous-modulaire des variables  i , j .

Applications

• Une matrice de Monge carrée qui est également symétrique par rapport à sa diagonale principale est appelée une matrice de Supnick (d'après Fred Supnick ); ce type de matrice a des applications au problème du voyageur de commerce (à savoir, que le problème admet des solutions faciles lorsque la matrice de distance peut être écrite comme une matrice de Supnick). Toute combinaison linéaire de matrices Supnick est elle-même une matrice Supnick.

Les références

• Deineko, Vladimir G .; Woeginger, Gerhard J. (octobre 2006). "Quelques problèmes concernant les vendeurs ambulants, les fléchettes et les pièces en euros" (PDF) . Bulletin de l'Association européenne pour l'informatique théorique . EATCS . 90 : 43-52. ISSN  0252-9742 .