A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources

DOI10.1016/S0167-6377(98)00053-4zbMath0956.90019OpenAlexW1967185041MaRDI QIDQ1306364

Dorit S. Hochbaum, Gerhard J. Woeginger

Publication date: 1999

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(98)00053-4

zbMATH Keywords

transportation problemlinear-time algorithmbottleneck transportation problembottleneck cost

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (3)

Risk-control approach for bottleneck transportation problem with randomness and fuzziness ⋮ A faster polynomial algorithm for the unbalanced Hitchcock transportation problem ⋮ A heuristic for obtaining better initial feasible solution to the transportation problem

Cites Work

• Unnamed Item
• Unnamed Item
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• A theorem on flows in networks
• An optimal algorithm for \(2 \times{} n\) bottleneck transportation problems
• Submodular functions and optimization
• An augmenting path method for solving linear bottleneck transportation problems
• An instant solution of the \(2\times n\) bottleneck transportation problem
• Time bounds for selection
• An O(n) algorithm for the multiple-choice knapsack linear program
• Fast Algorithms for Bipartite Network Flow
• Linear Programming in Linear Time When the Dimension Is Fixed
• A Linear Time Algorithm for a $2 \times n$ Transportation Problem
• The bottleneck transportation problem
• A Short Proof of the Factor Theorem for Finite Graphs

This page was built for publication: A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources