Editing Monge array

{{Short description|Type of mathematical object}}
{{refimprove|date=September 2012}}
In mathematics applied to [[computer science]], '''Monge arrays''', or '''Monge matrices''', are mathematical objects named for their discoverer, the French mathematician [[Gaspard Monge]].

An ''m''-by-''n'' [[matrix (mathematics)|matrix]] is said to be a ''Monge array'' if, for all <math>\scriptstyle i,\, j,\, k,\, \ell</math> such that

:<math>1\le i < k\le m\text{ and }1\le j < \ell\le n</math>

one obtains<ref name="Burkard1996">{{cite journal
| journal= Discrete Applied Mathematics
| first1 = Rainer E. | last1 = Burkard
| first2 = Bettina | last2 = Klinz
| first3 = Rüdiger | last3 = Rudolf
| title = Perspectives of Monge properties in optimization
| publisher = ELSEVIER 
| volume = 70 
| year = 1996
| issue = 2 
| pages = 95–96
 | doi=10.1016/0166-218x(95)00103-x
| doi-access = }}</ref>

:<math>A[i,j] + A[k,\ell] \le A[i,\ell] + A[k,j].\,</math>

So for any two rows and two columns of a Monge array (a 2&nbsp;&times;&nbsp;2 sub-matrix) the four elements at the intersection points have the property that the sum of the upper-left and lower right elements (across the [[main diagonal]]) is less than or equal to the sum of the lower-left and upper-right elements (across the [[antidiagonal]]).

This matrix is a Monge array:
:<math>
\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}</math>

For example, take the intersection of rows 2 and 4 with columns 1 and 5.
The four elements are:
:<math>
\begin{bmatrix}
17 & 23\\
11 & 7 \end{bmatrix}</math>

: 17 + 7 = 24
: 23 + 11 = 34

The sum of the upper-left and lower right elements is less than or equal to the sum of the lower-left and upper-right elements.

==Properties==
*The above definition is equivalent to the statement
:A matrix is a Monge array [[if and only if]] <math>A[i,j] + A[i+1,j+1]\le A[i,j+1] + A[i+1,j]</math> for all <math>1\le i < m</math> and <math>1\le j < n</math>.<ref name="Burkard1996"/>

*Any subarray produced by selecting certain rows and columns from an original Monge array will itself be a Monge array.
*Any [[linear combination]] with non-negative coefficients of Monge arrays is itself a Monge array.
*Every Monge array is totally monotone, meaning that its row minima occur in a nondecreasing sequence of columns, and that the same property is true for every subarray. This property allows the row minima to be found quickly by using the [[SMAWK algorithm]]. If you mark with a circle the leftmost minimum of each row, you will discover that your circles march downward to the right; that is to say, if <math>f(x) = \arg\min_{i\in \{1,\ldots,m\}} A[x,i]</math>, then <math>f(j)\le f(j+1)</math> for all <math>1\le j < n</math>. Symmetrically, if you mark the uppermost minimum of each column, your circles will march rightwards and downwards. The row and column ''maxima'' march in the opposite direction: upwards to the right and downwards to the left.
*The notion of ''weak Monge arrays'' has been proposed; a weak Monge array is a square ''n''-by-''n'' matrix which satisfies the Monge property <math>A[i,i] + A[r,s]\le A[i,s] + A[r,i]</math> only for all <math>1\le i < r,s\le n</math>.
*Monge matrix is just another name for [[supermodular function|submodular function]] of two discrete variables. Precisely, ''A'' is a Monge matrix if and only if ''A''[''i'',''j''] is a submodular function of variables&nbsp;''i'',''j''.

==Applications==
Monge matrices has applications in [[combinatorial optimization]] problems:
*When the [[traveling salesman problem]] has a cost matrix which is a Monge matrix it can be solved in quadratic time.<ref name="Burkard1996" /><ref name=":0">{{Cite journal |last1=Burkard |first1=Rainer E. |last2=Deineko |first2=Vladimir G. |last3=van Dal |first3=René |last4=van der Veen |first4=Jack A. A. |last5=Woeginger |first5=Gerhard J. |date=1998 |title=Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey |url=http://epubs.siam.org/doi/10.1137/S0036144596297514 |journal=SIAM Review |language=en |volume=40 |issue=3 |pages=496–546 |doi=10.1137/S0036144596297514 |bibcode=1998SIAMR..40..496B |issn=0036-1445}}</ref>
*A square Monge matrix which is also symmetric about its [[main diagonal]] is called a ''[[Supnick matrix]]'' (after [[Fred Supnick]]). Any linear combination of Supnick matrices is itself a Supnick matrix,<ref name="Burkard1996" /> and when the cost matrix in a traveling salesman problem is Supnick, the optimal solution is a predetermined route, unaffected by the specific values within the matrix.<ref name=":0" />

== References ==
{{Reflist}}
* {{cite journal | title = Some problems around travelling salesmen, dart boards, and euro-coins | first1 = Vladimir G. | last1 = Deineko | first2 =  Gerhard J. | last2 = Woeginger | author2-link = Gerhard J. Woeginger | journal = Bulletin of the European Association for Theoretical Computer Science | publisher = [[European Association for Theoretical Computer Science|EATCS]] | volume = 90 |date=October 2006 | issn = 0252-9742 | pages = 43–52 | url = http://alexandria.tue.nl/openaccess/Metis211810.pdf }}

[[Category:Theoretical computer science]]