On the role of bottleneck Monge matrices in combinatorial optimization

In this short summary of research the paper describes some significant aspects of exploiting the bottleneck Monge property in combinatorial optimization. A matrix (cij) is said to fulfill the bottleneck Monge property or to be a max distribution matrix, if max(cip,cjq)•max(ciq,cjp) for all 1•i<j•m, 1•p<q•n. Several problems of discrete programming can immediately be solved, if the underlying data have this property, in particular flow shop problems with minimum makespan, time transportation problems and bottleneck travelling salesman problems.