1
$\begingroup$

If $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ is the cost-matrix of an assignment problem, then the usual statement of the problem of finding an optimal assignment is to identify $n$ elements $a_{i,\,\pi(i)},\ i=1\cdots n$ of least cost-sum, i.e. to directly determine the solution set from $\boldsymbol{A}$ by modifying its entries e.g. according to the Hungarian algorithm.

Question:

can the following interpretation of the assignment problem fail to report the optimal solution:

determine the sequence of line-exchanges that renders the sum of the diagonal-elements optimal?


If the permutation-formulation also generates the optimal solution to the assignment problem, that would yield a greedy algorithm:

Exchanging two lines also exchanges two on-diagonal elements with two off-diagonal elements with known effect on the cost-sum of the elements on the diagonal.
It doesn't seem reasonable to exchange a pair of lines that doesn't bring about the maximal cost-reduction for the elements on the diagonal.

Addendum:
as the counter example of Brendan McKay shows, swapping pairs of rows or columns may not suffice to find the optimal assignment.
A preprocessing step that can deal with the counter example would be to first rotate the columns until the diagonal-elements have optimal cost-sum and only then strive for further improvements via swapping pairs of rows or columns.
It may even be necessary to interleave line-swapping with column-rotations frequently so that the elements on the principal diagonal always have better cost-sum than the elements on other diagonals.

$\endgroup$
2
  • $\begingroup$ There will be cases where all row swaps makes it worse but the global maximum is elsewhere. $\endgroup$ May 28 at 9:45
  • $\begingroup$ @BrendanMcKay is that also true if not only row swaps but also column swaps are checked for optimization potential? Would be nice to have a concrete example of such a situation. $\endgroup$ May 28 at 10:18

1 Answer 1

4
$\begingroup$

$$\pmatrix{ 2&3&0&0\\0&2&3&0\\0&0&2&3\\3&0&0&2}$$

Every swap of two columns or swap of two rows decreases the trace. However, there is a permutation putting all the 3s on the diagonal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.