Perspectives of Monge properties in optimization

An m x n matrix C is called Monge matrix if c(ij) + c(rs) less than or equal to c(is) + c(rj) for all 1 less than or equal to i < r less than or equal to m, 1 less than or equal to j < s less than or equal to n. In this paper we present a survey on Monge matrices and related Monge properties and their role in combinatorial optimization. Specifically, we deal with the following three main topics: (i) fundamental combinatorial properties of Monge structures, (ii) applications of Monge properties to optimization problems and (iii) recognition of Monge properties.