Article ID: | iaor19961689 |
Country: | Germany |
Volume: | 42 |
Issue: | 2 |
Start Page Number: | 161 |
End Page Number: | 168 |
Publication Date: | Sep 1995 |
Journal: | Mathematical Methods of Operations Research (Heidelberg) |
Authors: | Woeginger G.J., Rudolf R. |
The authors present an additive characterization of Monge matrices based on the extremal rays of the cone of nonnegative Monge matrices. By using this characterization, a simple proof for an old result by Supnick on the traveling salesman problem on Monge matrices is derived.