On a Subroutine for Covering Zeros in Hungarian Algorithm

The Hungarian algorithm is one of the most well-known methods in computer science literature. By this method, in each step the cost matrix is systematically reduced to a new matrix in order to obtain an optimal solution for the assignment problem. The subroutine of the algorithm includes determining the minimum number of lines needed to cover all zeros in the reduced cost matrix and modifying the matrix according to the number of lines. In this paper, firstly the methods in literature including the covering all zeros with a minimum number of lines are examined, then a new method is proposed and computational experiments are discussed.

Macar Algoritmasýnýn Sýfýrlarý Kapatma Alt Yordamý Üzerine

Macar algoritmasý bilgisayar bilimleri literatüründe en çok bilinen yöntemlerden birisidir. Bu yöntem ile maliyet matrisi her adýmda sistematik bir þekilde yeni bir indirgenmiþ matrise dönüþtürülerek atama problemine çözüm getirilmektedir. Algoritmanýn alt yordamýnda matriste sýfýr içeren tüm hücreler en az sayýda çizgi ile kapatýlmakta ve çizgilerin durumuna göre matris üzerinde iþlem yapýlmaktadýr. Bu makalede literatürdeki en az sayýda çizgi ile kapatma teknikleri incelenecek ve yeni bir yöntem önerisinde bulunularak hesaplama denemelerinin sonuçlarý tartýþýlacaktýr.