The cone of Monge matrices : extremal rays and applications

R. Rudolf; G.J. Woeginger

doi:10.1007/BF01415751

The cone of Monge matrices : extremal rays and applications

R. Rudolf, G.J. Woeginger

Research output: Contribution to journal › Article › Academic › peer-review

16 Citations (Scopus)

2 Downloads (Pure)

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.

Original language	English
Pages (from-to)	161-168
Number of pages	8
Journal	Mathematical Methods of Operations Research
Volume	42
Issue number	2
DOIs	https://doi.org/10.1007/BF01415751
Publication status	Published - 1995

Access to Document

10.1007/BF01415751

Cite this

@article{d6cc97c6a26c40049108574d26eb78a1,

title = "The cone of Monge matrices : extremal rays and applications",

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.",

author = "R. Rudolf and G.J. Woeginger",

year = "1995",

doi = "10.1007/BF01415751",

language = "English",

volume = "42",

pages = "161--168",

journal = "Mathematical Methods of Operations Research",

issn = "1432-2994",

publisher = "Physica-Verlag",

number = "2",

}

TY - JOUR

T1 - The cone of Monge matrices : extremal rays and applications

AU - Rudolf, R.

AU - Woeginger, G.J.

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

U2 - 10.1007/BF01415751

DO - 10.1007/BF01415751

M3 - Article

SN - 1432-2994

VL - 42

SP - 161

EP - 168

JO - Mathematical Methods of Operations Research

JF - Mathematical Methods of Operations Research

IS - 2

ER -

The cone of Monge matrices : extremal rays and applications

Abstract

Access to Document

Fingerprint

Cite this