# fastest algorithm for rectangular linear assignment problem

I want to optimally assign $$m$$ jobs equally to $$n$$ workers, where $$m>n$$. Assume $$m = an$$ for some integer $$a$$, so that each worker must get exactly $$a$$ jobs. (The rectangular linear assignment problem, as defined here). I know this can be done by duplicating the workers to have $$a$$ copies of each, and then solving using the Kuhn-Munkres algorithm, which would result in $$O(m^3)$$.

This is an upper bound on the complexity of my problem. Is it also a lower bound? Is my problem in fact $$\Theta(m^3)$$? I.e., is the method of duplicating workers and using Kuhn-Munkres (as fast as) the fastest algorithm for solving the rectangular linear assignment problem (RLAP)?.

I want to know because I have a reduction of RLAP to another problem, and I want to lower-bound the complexity of this other problem.

• What is the "rectangular linear assignment problem"?
– D.W.
Commented Aug 17, 2022 at 16:28
• "The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs" - researchgate.net/publication/… Commented Aug 18, 2022 at 9:56

No, $$\Omega(m^3)$$ is not a lower bound. Your problem can be solved in $$O((nm)^{1 + o(1)} \log a)$$ time, by reducing to max flow and then using a state-of-the-art min cost max flow algorithm, such as the recent algorithm by Chen et al. See also https://en.wikipedia.org/wiki/Maximum_flow_problem#Algorithms.
There is a trivial $$\Omega(nm)$$ lower bound, since you have a weight for each pair of worker and job, and it requires $$\Omega(nm)$$ just to read in all of those weights.
• Thanks, I guess this shows it is not $\Theta(m^3)$ anyway. What I am really interested in is a lower bound though. Commented Aug 18, 2022 at 10:46
• @ludog, see revised answer, where I have corrected a mistake in my prior answer and provided a lower bound. I answered the question you asked (is $\Omega(m^3)$ a lower bound?). Feedback for the future: If what you really wanted was the best possible lower bound, it would be better to ask for that explicitly from the start.