We have $n$ tasks, each has its own price: $a_i$. We also have $n$ workers, each can do task $i$ with a probability $b_i^k$. Each worker should do only 1 task. I am trying to find out what will be the best algorithm to maximize the expectation of money that workers can earn (this will be a sum: $\sum\limits_i a_ib_i^{k_i},$where $k_i$ are some permutation of $1,..n$).

My idea was to sort probabilities of success for each of the tasks and compare products of its prices and difference of the top 2 probabilities. When I will get the maximum of such function, I will assign this task to a worker with the best probability to successfully finish it and after that do the whole procedure again. Unfortunately, I was stuck trying to prove it, also I am not even sure that this is the best possible algorithm. I will really appreciate any help or a hint.

  • $\begingroup$ You can always rephrase it as an IP problem if nothing else, however, I doubt that this is the solution you need. If the defining matrix is totally unimodular, it is not that bad, otherwise it may be worth finding a faster algorithm. $\endgroup$ – rss Apr 30 at 15:06
  • 2
    $\begingroup$ Hint: matching. $\endgroup$ – Marcus Ritt Apr 30 at 19:06

What you are describing is a "greedy heuristic", and no, it is not guaranteed to find an optimal assignment. To expand on the comment by Marcus Ritt, see this description of the assignment problem.

  • $\begingroup$ Thank you very much! This is exactly what I was looking for. $\endgroup$ – AO1992 May 3 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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