An algorithm for the detection and construction of Monge sequences

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

Research output: Contribution to journalArticle

24 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 languageEnglish (US)
Pages (from-to)669-680
Number of pages12
JournalLinear Algebra and Its Applications
Volume114-115
Issue numberC
DOIs
StatePublished - 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'An algorithm for the detection and construction of Monge sequences'. Together they form a unique fingerprint.

  • Cite this