Editing Monge array (section)

==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" />