A strongly polynomial algorithm for the transportation problem

DOI10.1007/BF01585755zbMath0833.90084MaRDI QIDQ1804365

H. Schannath, Peter Kleinschmidt

Publication date: 14 May 1995

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

excess scalingstrongly polynomial algorithmlinear transportation problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (23)

Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Ergonomic workplace design in the fast pick area ⋮ An iterative algorithm for two level hierarchical time minimization transportation problem ⋮ Optimal radio resources and transmission formats assignment in OFDMA systems ⋮ A feasible flow-based iterative algorithm for the two-level hierarchical time minimization transportation problem ⋮ Scheduling last-mile deliveries with truck-based autonomous robots ⋮ Unnamed Item ⋮ Coordination mechanisms for parallel machine scheduling ⋮ Tropical medians by transportation ⋮ A solution technique for capacitated two-level hierarchical time minimization transportation problem ⋮ Unnamed Item ⋮ Uniform capacitated facility location problem with random input data ⋮ First-order dominance: stronger characterization and a bivariate checking algorithm ⋮ A Solution Concept Related to “Bounded Rationality” for some Two-Echelon Models ⋮ On the transportation problem with market choice ⋮ BOUNDING WRONG‐WAY RISK IN CVA CALCULATION ⋮ Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph ⋮ Rényi 100, quantitative and qualitative (in)dependence ⋮ Bilevel time minimizing transportation problem ⋮ Two level hierarchical time minimizing transportation problem ⋮ Covering partially directed graphs with directed paths ⋮ A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

Cites Work

• Signature Methods for the Assignment Problem
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems
• Solving the Assignment Problem by Relaxation
• Improved Algorithms for Bipartite Network Flow

This page was built for publication: A strongly polynomial algorithm for the transportation problem