The given maximization assignment problem can be converted into a minimization…
2014
The given maximization assignment problem can be converted into a minimization problem by
- A.
subtracting each entry in a column from the maximum value in that column.
- B.
subtracting each entry in the table from the maximum value in that table.
- C.
adding each entry in a column from the maximum value in that column.
- D.
adding maximum value of the table to each entry in the table.
Attempted by 25 students.
Show answer & explanation
Correct answer: B
Answer: Subtract each entry in the table from the maximum value in that table.
Key idea: Transforming each profit a_ij into (M − a_ij), where M is the largest entry in the entire matrix, converts the maximization of total profit into minimization of total cost without changing which assignment is optimal.
Step 1: Find the maximum value M in the whole profit table.
Step 2: Replace each entry a_ij with M − a_ij. Solve the assignment problem on this new matrix by minimization.
Why it works: For any complete assignment, the total transformed cost equals (#assignments)×M minus the original total profit. Since the first term is constant across assignments, minimizing the transformed cost is equivalent to maximizing the original profit.
Note: An alternative is to subtract each entry from the maximum of its column (or row); this also produces an equivalent minimization for square assignment problems because it shifts each column by a constant. The global-maximum method is the simplest and commonly used approach.