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 tha n 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 Mong e properties and their role in combinatorial optimization. Specificall y, we deal with the following three main topics: (i) fundamental combi natorial properties of Monge structures, (ii) applications of Monge pr operties to optimization problems and (iii) recognition of Monge prope rties.