The Hungarian algorithm for the linear sum assignment problem with dimension $n$ has complexity $O(n^3)$. Can the complexity be improved if one is able to assume that the cost matrix is structured? I am particularly thinking of the case where the cost matrix is low-rank, or sparse, or banded.
Furthermore, it seems to me that if the cost matrix is a block matrix with $b$ equally-sized blocks, and off-diagonal blocks with elements equal to $+\infty$, then the problem decomposes into $b$ separate subproblems of size $n/b$, leading to complexity $O(b (n/b)^3) = O(n^3/b^2)$. Is this correct?