The cone of Monge matrices: Extremal rays and applications |
| |
| Authors: | Rüdiger Rudolf Gerhard J. Woeginger |
| |
| Affiliation: | (1) TU Graz, Institut für Mathematik B, Steyrergasse 30, 8010 Graz, Austria |
| |
| Abstract: | We 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 (1957) on the traveling salesman problem on Monge matrices is derived.This research has been supported by the Spezialforschungsbereich F 003  Optimierung und Kontrolle , Projektbereich Diskrete Optimierung. |
| |
| Keywords: | Combinatorial optimization traveling salesman problem Monge matrix cone |
| 本文献已被 SpringerLink 等数据库收录！ |
