# zbMATH — the first resource for mathematics

Perspectives of Monge properties in optimization. (English) Zbl 0856.90091
Summary: An $$m\times n$$ matrix $$C$$ is called Monge matrix if $$c_{ij}+ c_{rs}\leq c_{is}+ c_{rj}$$ for all $$1\leq i< r\leq m$$, $$1\leq j< s\leq n$$. 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.

##### MSC:
 90C27 Combinatorial optimization 05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
##### Keywords:
recognition problems; Monge matrix
Full Text: