Monge array

I matematik tillämpad på datavetenskap är Monge-matriser , eller Monge - matriser , matematiska objekt uppkallade efter deras upptäckare, den franske matematikern Gaspard Monge .

En m -by- n matris sägs vara en Monge-matris om, för alla $\scriptstyle i,\,j,\,k,\,\ell$ så att

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

man får

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

Så för två rader och två kolumner i en Monge-matris (en 2 × 2 submatris) har de fyra elementen vid skärningspunkterna egenskapen att summan av de övre vänstra och nedre högra elementen (tvärs över huvuddiagonalen ) är mindre än eller lika med summan av de nedre vänstra och övre högra elementen (tvärs över antidiagonalen ) .

Denna matris är en Monge-array:

$&22&16&29&$

Ta till exempel skärningspunkten mellan raderna 2 och 4 med kolumnerna 1 och 5. De fyra elementen är:

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

17 + 7 = 24

23 + 11 = 34

Summan av de övre vänstra och nedre högra elementen är mindre än eller lika med summan av de nedre vänstra och övre högra elementen.

Egenskaper

• Ovanstående definition är ekvivalent med påståendet

En matris är en Monge-matris om och endast om ${\displaystyle A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]} för$ alla $1\leq i<m$ och $1\leq j<n$ .

• Varje undermatris som skapas genom att välja vissa rader och kolumner från en original Monge-array kommer i sig att vara en Monge-array.
• Varje linjär kombination med icke-negativa koefficienter för Monge-matriser är i sig en Monge-matris.
• En intressant egenskap hos Monge-arrayer är att om du markerar med en cirkel det lägsta till vänster på varje rad, kommer du att upptäcka att dina cirklar marscherar nedåt till höger; det vill säga, om $f(x)=\arg \min _{i\in \{1, \ldots ,m\}}A[x,i]$ , sedan $f(j)\leq f(j+1)$ för alla $1\leq j<n$ . Symmetriskt, om du markerar det översta minimum av varje kolumn, kommer dina cirklar att marschera åt höger och nedåt. Rad- och kolumnmaxima marscherar i motsatt riktning: uppåt till höger och nedåt till vänster.
• Begreppet svaga Monge-arrayer har föreslagits; en svag Monge-matris är en kvadratisk n -by- n -matris som $A[ i,i]+A[r,s]\leq A[i,s]+A[r,i]$ Monge-egenskapen endast för alla $1\leq i<r,s \leq n$ .
• Varje Monge-array är helt monoton, vilket betyder att dess radminima förekommer i en icke-minskande sekvens av kolumner, och att samma egenskap gäller för varje subarray. Den här egenskapen gör att radminima kan hittas snabbt genom att använda SMAWK - algoritmen .
• Monge matris är bara ett annat namn för submodulär funktion av två diskreta variabler. Exakt, A är en Monge-matris om och endast om A [ i , j ] är en submodulär funktion av variablerna i , j .

Ansökningar

• En kvadratisk Monge-matris som också är symmetrisk kring sin huvuddiagonal kallas en Supnick-matris (efter Fred Supnick); den här typen av matris har tillämpningar på resandeförsäljarproblemet ( nämligen att problemet medger enkla lösningar när avståndsmatrisen kan skrivas som en Supnick-matris). Varje linjär kombination av Supnick-matriser är i sig en Supnick-matris.

•   Deineko, Vladimir G.; Woeginger, Gerhard J. (oktober 2006). "Några problem kring resande försäljare, darttavlor och euromynt" ( PDF) . Bulletin från European Association for Theoretical Computer Science . EATCS . 90 : 43–52. ISSN 0252-9742 .