A greedy algorithm for assignment and transportation problems

Abstract The transportation and the assignment problems have both been frequently investigated in the field of operations research. For a couple of decades, it has been proven that no greedy algorithm can yield an optimal solution to these problems since their respective underlying structures are not matroids. It is shown in this paper that, even though seeking a greedy algorithm to solve one of the aforesaid problems is fanciful, a heuristic method capable of providing good approximations to the optimal solution can be found. The so-called “hybrid greedy algorithm” is a hybridization of the Balas-Hammer and the Hungarian methods. It can be used to solve both the transportation and the assignment problems. It often provides an optimal solution to small assignment problems and it outperforms the Balas-Hammer (Vogel’s approximation method) and other heuristic methods for solving the transportation problem.JEL Classification: C02 , C61 , C63 MSC Classification: 00A72 , 03D15 , 68Q25 , 68U20 , 68W40 , 90C27