1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What is the "rectangular linear assignment problem"? $\endgroup$
    – D.W.
    Commented Aug 17, 2022 at 16:28
  • $\begingroup$ "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/… $\endgroup$
    – ludog
    Commented Aug 18, 2022 at 9:56

1 Answer 1

1
$\begingroup$

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.

These two bounds are nearly matching.

$\endgroup$
2
  • $\begingroup$ Thanks, I guess this shows it is not $\Theta(m^3)$ anyway. What I am really interested in is a lower bound though. $\endgroup$
    – ludog
    Commented Aug 18, 2022 at 10:46
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented Aug 18, 2022 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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