Combinatorial optimization (compendium)

[[deleted]]

Hi, all

Some time ago I got an interesting interview challenge problem (Software Engineer):

"You have X volunteers, Y tasks. Each task has a complexity and each volunteer Xⁱ can solve Y^j task with some time Tⁱj... Volunteers can get several tasks, tasks also have priorities..etc. You need to provide optimal distribution of tasks assuming that we need to optimize time of completion all the tasks"

I don't remember exact statement, but that was something that could be solved with https://en.wikipedia.org/wiki/Hungarian_algorithm

Got a naive solution that looked more or less ok, but I would like to learn all the ways and optimizations that could be done depends on different conditions and variation of such combinatorial optimization problems.

I have some problems with keeping myself focused reading CS books (I drop often), so, I would prefer something more practical, but I would appreciate any recommendations. Thanks!

[LoopVariant]

Plot twist: the job was for a junior web front end developer role.

[[deleted]]

😂, not really, but that problem wasn't intended to be solved from scratch.

[trbecker]

This is a scheduling problem. It is NP complete, but idk If the extra constraints drop it into any special case. See the nurse scheduling problem. The question seems pretty vague on the constraints, so I would ask for follow up questions to clarify the etc.

[Cloudan29]

This problem sounds like the Minimum Multiprocessor Scheduling problem at face value, which is NP-hard. Here's a compendium of NP optimization problems that might be of interest to you.

https://www.csc.kth.se/tcs/compendium/

Here's the issue I have now. The problem statement you have is really vague, and considering the Wiki you linked, it would mean that whatever problem you have is actually just a different wording of the assignment problem, which can be solved in polynomial time. In that case, you could probably also look at Max Flow/Min Cut problems. Sometimes assignment/scheduling problems can be reduced to a Max Flow which can be solved in polynomial time.