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?
-
$\begingroup$ Algorithms for maximum weight bipartite maximum matching are unfortunately more complicated than that. They don't really follow the greedy paradigm. $\endgroup$Yuval Filmus– Yuval Filmus2017年04月07日 06:05:35 +00:00Commented Apr 7, 2017 at 6:05
1 Answer 1
The answer of your post question (already given in Yuval comment) is that there is no greedy techniques providing you the optimal answer to an assignment problem.
The commonly used solution is the Hungarian algorithm, see
Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955
for the original paper.
Otherwise your solution seems correct to me, and as usually with greedy algorithms, it will provide you a feasible solution which you may hope to not be "too far" from the global optimal solution.
Explore related questions
See similar questions with these tags.