### 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 | |

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

## 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

*Linear Algebra and Its Applications*,

*114-115*(C), 669-680. https://doi.org/10.1016/0024-3795(89)90487-4