Monge array

<h2 id="properties">Properties</h2>
<ul><li>The above definition is equivalent to the statement</li></ul>
A matrix is a Monge array <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> 
 
 
 
 A
 [
 i
 ,
 j
 ]
 +
 A
 [
 i
 +
 1
 ,
 j
 +
 1
 ]
 ≤
 A
 [
 i
 ,
 j
 +
 1
 ]
 +
 A
 [
 i
 +
 1
 ,
 j
 ]
 
 
 {\displaystyle A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]}
 
 for all 
 
 
 
 1
 ≤
 i
 <
 m
 
 
 {\displaystyle 1\leq i<m}
 
 and 
 
 
 
 1
 ≤
 j
 <
 n
 
 
 {\displaystyle 1\leq j<n}
 
.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
<ul><li>Any subarray produced by selecting certain rows and columns from an original Monge array will itself be a Monge array.</li>
<li>Any <a href="/facts/Linear_combination/CVjL6kuN">linear combination</a> with non-negative coefficients of Monge arrays is itself a Monge array.</li>
<li>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 <a href="/facts/SMAWK_algorithm/tFbuohlK">SMAWK algorithm</a>. 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 
 
 
 
 f
 (
 x
 )
 =
 arg
 ⁡
 
 min
 
 i
 ∈
 {
 1
 ,
 …
 ,
 m
 }
 
 
 A
 [
 x
 ,
 i
 ]
 
 
 {\displaystyle f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]}
 
, then 
 
 
 
 f
 (
 j
 )
 ≤
 f
 (
 j
 +
 1
 )
 
 
 {\displaystyle f(j)\leq f(j+1)}
 
 for all 
 
 
 
 1
 ≤
 j
 <
 n
 
 
 {\displaystyle 1\leq j<n}
 
. 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.</li>
<li>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 
 
 
 
 A
 [
 i
 ,
 i
 ]
 +
 A
 [
 r
 ,
 s
 ]
 ≤
 A
 [
 i
 ,
 s
 ]
 +
 A
 [
 r
 ,
 i
 ]
 
 
 {\displaystyle A[i,i]+A[r,s]\leq A[i,s]+A[r,i]}
 
 only for all 
 
 
 
 1
 ≤
 i
 <
 r
 ,
 s
 ≤
 n
 
 
 {\displaystyle 1\leq i<r,s\leq n}
 
.</li>
<li>Monge matrix is just another name for <a href="/facts/Supermodular_function/EkrRrU0f">submodular function</a> of two discrete variables. Precisely, A is a Monge matrix if and only if A[i,j] is a submodular function of variables i,j.</li></ul>
<h2 id="applications">Applications</h2>
Monge matrices has applications in <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a> problems:

<ul><li>When the <a href="/facts/Traveling_salesman_problem/2WEKVLnV">traveling salesman problem</a> has a cost matrix which is a Monge matrix it can be solved in quadratic time.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>A square Monge matrix which is also symmetric about its <a href="/facts/Main_diagonal/rkT2F08Q">main diagonal</a> is called a <a href="/facts/Supnick_matrix/Pkjy2bne">Supnick matrix</a> (after Fred Supnick). Any linear combination of Supnick matrices is itself a Supnick matrix,<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> 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.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li></ul>

<ul><li>Deineko, Vladimir G.; <a href="/facts/Gerhard_J._Woeginger/beUa9kJr">Woeginger, Gerhard J.</a> (October 2006). <a href="http://alexandria.tue.nl/openaccess/Metis211810.pdf">"Some problems around travelling salesmen, dart boards, and euro-coins"</a> (PDF). Bulletin of the European Association for Theoretical Computer Science. 90. <a href="/facts/European_Association_for_Theoretical_Computer_Science/4jlopeDl">EATCS</a>: 43–52. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0252-9742">0252-9742</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Burkard, Rainer E.; Klinz, Bettina; Rudolf, Rüdiger (1996). "Perspectives of Monge properties in optimization". Discrete Applied Mathematics. 70 (2). ELSEVIER: 95–96. doi:10.1016/0166-218x(95)00103-x. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Burkard, Rainer E.; Klinz, Bettina; Rudolf, Rüdiger (1996). "Perspectives of Monge properties in optimization". Discrete Applied Mathematics. 70 (2). ELSEVIER: 95–96. doi:10.1016/0166-218x(95)00103-x. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Burkard, Rainer E.; Klinz, Bettina; Rudolf, Rüdiger (1996). "Perspectives of Monge properties in optimization". Discrete Applied Mathematics. 70 (2). ELSEVIER: 95–96. doi:10.1016/0166-218x(95)00103-x. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Burkard, Rainer E.; Deineko, Vladimir G.; van Dal, René; van der Veen, Jack A. A.; Woeginger, Gerhard J. (1998). "Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey". SIAM Review. 40 (3): 496–546. Bibcode:1998SIAMR..40..496B. doi:10.1137/S0036144596297514. ISSN 0036-1445. <a href="http://epubs.siam.org/doi/10.1137/S0036144596297514" target="_blank">http://epubs.siam.org/doi/10.1137/S0036144596297514</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Burkard, Rainer E.; Klinz, Bettina; Rudolf, Rüdiger (1996). "Perspectives of Monge properties in optimization". Discrete Applied Mathematics. 70 (2). ELSEVIER: 95–96. doi:10.1016/0166-218x(95)00103-x. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Burkard, Rainer E.; Deineko, Vladimir G.; van Dal, René; van der Veen, Jack A. A.; Woeginger, Gerhard J. (1998). "Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey". SIAM Review. 40 (3): 496–546. Bibcode:1998SIAMR..40..496B. doi:10.1137/S0036144596297514. ISSN 0036-1445. <a href="http://epubs.siam.org/doi/10.1137/S0036144596297514" target="_blank">http://epubs.siam.org/doi/10.1137/S0036144596297514</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Monge array open-in-new

Monge array