imported>Cewbot: Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{Sys rating}}.

2024-02-06T09:11:15Z

Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{Sys rating}}.

New page

{{WikiProject banner shell|class=Start|
{{WikiProject Systems|importance=mid |field=Operations research}}
}}
== Need applications ==

The thing that's missing here is an explanation of why anyone would care about a Monge array. [[User:Dominus|Dominus]] 10:27 20 May 2003 (UTC)

I don't have the proof with me, but it has to do with keeping search and sort algorithms, like [[divide and conquer]], within O(nlogn) time. [[User:Poor Yorick|Poor Yorick]]

I removed this sentence, until such time as someone can explain how it's true. —ajo, 5 Apr 2005
:*Monge arrays are useful for keeping [[Big O notation|growth of functions]] in O(''n'' log ''n'') time.

:I agree, need more applications to motivate why we care about these matrices or what's interesting about them. Evidently if they're widely known in CS, such applications exist. [[User:Deco|Deco]] 22:52, 10 August 2006 (UTC)

A Monge matrix M has the nice property that both M and its transpose are ''Completely Monotone'' (which needs an entry itself). The row minima or maxima of a completly monotone matrix can be found efficiently <math>O(n)</math> time (rather in <math>O(n^2)</math> trivially) using an algorithm known as SMAWK <ref>Agarwal, Klawe, Moran, Shor, and Wilbur, Geometric applications of a matrix searching algorithm, Algorithmica 2, pp. 195-208 (1987)</ref>.
This was used, for example to obtain a sub-quadratic algorithm for string edit distance <ref> Crochemore, Landau and Ziv-ukelson, Symposium of Discrete Algorithms (SODA) 2002, pp. 679--688</ref> and for obtaining an efficient algorithm for the single source shortest path problem in planar graphs with negative weights <ref>Klein, Mozes and Weimann, SODA 2009</ref>
--[[User:Algoguy|Algoguy]] ([[User talk:Algoguy|talk]]) 17:25, 24 November 2008 (UTC)

{{reflist-talk}}

==Matrix or array?==

The definition in the article seems to be an abstract definition of a class of matrices, rather than a class of arrays - arrays are only part of the term used and one possible way of storing the matrix. In particular, it's rather difficult to construct arrays of arbitrary real numbers, such as the definition describes, in finite memory. In fact, I think the term is confusing enough that it may be helpful to actually point out some of this in the article itself. What does the author think?

[[User:Dcoetzee|Derrick Coetzee]] 16:26, 2 May 2004 (UTC)

:Well, it's had 9 "authors" already, including you - so I say you should '''[[WP:BBIEP|be bold]]''' and go ahead. This article could certainly use some actual text explaining things a bit better... - [[User:IMSoP|IMSoP]] 23:42, 17 Jun 2004 (UTC)

Yes, the term "array" is kind of CS-chauvinistic; when I reworked much of the text just now, I changed a lot of "array"s to "matrix"s. But according to Google, a lot of references talk about "Monge arrays," so it's certainly appropriate to use (or at least mention) the terminology that's been established in computer science, rather than (or in addition to) the terminology that's correct from a mathematical standpoint. —ajo, 5 Apr 2005

== Linear Combinations? ==

In mathematics, linear combinations usually include taking negative multiples of the components. So in particular, if monge arrays are really closed under linear combinations, then the negative of any monge array is a monge array. But this is obviously false.

Talk:Monge array - Revision history

imported>Cewbot: Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{Sys rating}}.