An algorithm for the detection and construction of Monge sequences

Noga Alon; Steven Cosares; Dorit S. Hochbaum; Ron Shamir

doi:10.1016/0024-3795(89)90487-4

An algorithm for the detection and construction of Monge sequences

Noga Alon, Steven Cosares, Dorit S. Hochbaum, Ron Shamir

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

27 Scopus citations

Abstract

We give an efficient algorithm which determines whether a condition due to Hoffman (1963) is satisfied by the cost matrix of a transportation problem. In case the condition is satisfied, our algorithm generates a permutation of the matrix entries (called a Monge sequence), which allows for the solution of any problem with that cost matrix in linear time, by way of a "greedy" algorithm. This is the first polynomial algorithm for this problem. The running time of our algorithm is better than that of the best known algorithms for the transportation problem, and thus it can be used as a preliminary step in solving such problems without an increase in the overall complexity.

Original language	English (US)
Pages (from-to)	669-680
Number of pages	12
Journal	Linear Algebra and Its Applications
Volume	114-115
Issue number	C
DOIs	https://doi.org/10.1016/0024-3795(89)90487-4
State	Published - 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Algebra and Number Theory
Numerical Analysis
Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0024-3795(89)90487-4

Cite this

@article{49423a52625147fab959b70b94077428,

title = "An algorithm for the detection and construction of Monge sequences",

abstract = "We give an efficient algorithm which determines whether a condition due to Hoffman (1963) is satisfied by the cost matrix of a transportation problem. In case the condition is satisfied, our algorithm generates a permutation of the matrix entries (called a Monge sequence), which allows for the solution of any problem with that cost matrix in linear time, by way of a {"}greedy{"} algorithm. This is the first polynomial algorithm for this problem. The running time of our algorithm is better than that of the best known algorithms for the transportation problem, and thus it can be used as a preliminary step in solving such problems without an increase in the overall complexity.",

author = "Noga Alon and Steven Cosares and Hochbaum, {Dorit S.} and Ron Shamir",

note = "Funding Information: *Supported in part by Allon Fellowship and by a Bat Sheva de Rothschild grant. {\textquoteleft}Supported in part by the National Science Foundation under grant ECS-G-01988 Office of Naval Research under grant NGOO 1488-KXI377. *Supported in part by Allon Fellowship.",

year = "1989",

doi = "10.1016/0024-3795(89)90487-4",

language = "English (US)",

volume = "114-115",

pages = "669--680",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

number = "C",

}

TY - JOUR

T1 - An algorithm for the detection and construction of Monge sequences

AU - Alon, Noga

AU - Cosares, Steven

AU - Hochbaum, Dorit S.

AU - Shamir, Ron

N1 - Funding Information: *Supported in part by Allon Fellowship and by a Bat Sheva de Rothschild grant. ‘Supported in part by the National Science Foundation under grant ECS-G-01988 Office of Naval Research under grant NGOO 1488-KXI377. *Supported in part by Allon Fellowship.

PY - 1989

Y1 - 1989

N2 - We give an efficient algorithm which determines whether a condition due to Hoffman (1963) is satisfied by the cost matrix of a transportation problem. In case the condition is satisfied, our algorithm generates a permutation of the matrix entries (called a Monge sequence), which allows for the solution of any problem with that cost matrix in linear time, by way of a "greedy" algorithm. This is the first polynomial algorithm for this problem. The running time of our algorithm is better than that of the best known algorithms for the transportation problem, and thus it can be used as a preliminary step in solving such problems without an increase in the overall complexity.

AB - We give an efficient algorithm which determines whether a condition due to Hoffman (1963) is satisfied by the cost matrix of a transportation problem. In case the condition is satisfied, our algorithm generates a permutation of the matrix entries (called a Monge sequence), which allows for the solution of any problem with that cost matrix in linear time, by way of a "greedy" algorithm. This is the first polynomial algorithm for this problem. The running time of our algorithm is better than that of the best known algorithms for the transportation problem, and thus it can be used as a preliminary step in solving such problems without an increase in the overall complexity.

UR - http://www.scopus.com/inward/record.url?scp=0011376367&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0011376367&partnerID=8YFLogxK

U2 - 10.1016/0024-3795(89)90487-4

DO - 10.1016/0024-3795(89)90487-4

M3 - Article

AN - SCOPUS:0011376367

SN - 0024-3795

VL - 114-115

SP - 669

EP - 680

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - C

ER -

An algorithm for the detection and construction of Monge sequences

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this