Is there a greedy algorithm to solve the assignment problem?

The assignment problem is defined as:

There are n people who need to be assigned to n jobs, one person per job. The cost that would accrue if the ith person is assigned to the jth job is a known quantity C[i,j] for each pair i, j = 1, 2, ..., n. The problem is to find an assignment with the minimum total cost.

There is a question asking to design a greedy algorithm to solve the problem. It also asks if the greedy algorithm always yields an optimal solution and for the performance class of the algorithm. Here is my attempt at designing an algorithm:

Am I correct in saying that my algorithm is of O(n^2)? Am I also correct in saying that a greedy algorithm does not always yield an optimal solution? I used my algorithm on the following cost matrix and it is clearly not the optimal solution. Did I Do something wrong?

• Algorithms for maximum weight bipartite maximum matching are unfortunately more complicated than that. They don't really follow the greedy paradigm. Apr 7, 2017 at 6:05