EXTENSION OF EGERVÀRY THEOREM ON OPTIMAL SOLUTION OF ASSIGNMENT PROBLEM: LOGICAL APPROACH

Abstract

A technique to solve the balanced linear assignment problem is introduced using graph theory and is based on logical approach. In the method, the aim is to find a matching in which the sum of weights of the edges is as large as possible, in a weighted bipartite graph. Generally it consists of finding a minimum-weight perfect matching and is a specialization of the maximum weight matching problem for bipartite graphs. The concept of decision matrix ([1]) is applied for finding last two assignments.