A note on the low-rank assignment problem

Recent research has investigated whether the complexity of the assignment problem can be parameterized by the rank of its weight (or cost) matrix. The underlying motivation is that when the rank of the weight matrix is one, the problem can be solved via a simple sorting procedure, which is much faster compared to the algorithms known for the general case. However, already for rank two, it remains unclear whether more efficient algorithms exist than those available when no restriction on the rank is assumed. We contribute a negative result, showing that an elementary structural property of the rank-one case does not extend to rank two. Concretely, for rank one it is trivial to verify that alternating 4-cycles always suffice to augment a nonoptimal solution. By contrast, we prove that for rank two arbitrarily long augmenting cycles may be required, and even more, for each constant k there are rank-two instances with exponentially-many nonoptimal solutions that are stable under augmentation along alternating k -cycles. We also present a geometric problem whose complexity lower-bounds that of low-rank assignment problems.