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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Burkard RE, Klinz B, Rudolf R (1994) Perspectives of monge properties in optimization, Report 2, SFB. Optimierung und Kontrolle. University of Technology Graz Austria, to appear in Discrete Applied Mathematics
Hoffman AJ (1961) On simple linear programming problems, in Convexity Proc Symposia in Pure Mathematics AMS Providence RI 317–327
Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1985) The traveling salesman problem. Wiley Chichester
Michalski M (1987) On a class of polynomially solvable travelling salesman problems. Zastosowania Matematyki (Applicationes Mathematicae) XIX 3–4:531–539
Monge G (1781) Mémoires sur la théorie des débais et des remblais. In Historie de l'Academie Royale des Science, Année M. DCCLXXXI, avec les Mémoires de Mathématique et de Physique, pour la même Année, Tirés des Registres de cette Académie 666–704
Park JK (1991) A special case of then-vertex traveling salesman problem that can be solved inO(n) time. Information Processing Letters 40:247–254
Supnick F (1957) Extremal hamiltonian lines. Annals of Math 66:179–201
Yao FF (1982) Speed-up in dynamic programming. SIAM Journal on Algebraic and Discrete Methods 3:532–540
Author information
Authors and Affiliations
Additional information
This research has been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung.
Rights and permissions
About this article
Cite this article
Rudolf, R., Woeginger, G.J. The cone of Monge matrices: Extremal rays and applications. ZOR - Methods and Models of Operations Research 42, 161–168 (1995). https://doi.org/10.1007/BF01415751
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01415751