0
$\begingroup$

Im trying to find an algorithm to solve the following problem:

We have a set of workers and some tasks, with not every worker being able to do any kind of task (but at least one). Theres is furthermore an optimal distribution of how many workers should be assigned to each task. Find an assignment of every worker to a task he can do, such that the actual distribution comes as close as possible to the optimal one. To put it formally:

Given:

  • $n$ Workers $W$, $m$ tasks
  • $V_1,...,V_m \subseteq W$ (the workers suitable for each task), $\quad w \in W \Rightarrow \exists i : w \in V_i$
  • $s_1,...,s_m \in \{0,..,n\}$ (the optimal number of workers for each task), $\quad \sum_{i=1}^m s_i = n$

Find $X_1,...,X_m$ such that

  • $X_i \subseteq V_i, \quad i=1,...,m \quad$ (the workers assigned to each task)
  • $\sum_{i=1}^m |X_i| = n, \quad \bigcup_{i=1}^m X_i = W \quad$ (every worker is assigned to exactly one task)
  • $d = \sum_{i=1}^m \left (|X_i| - s_i \right )^2$ is minimized

Can you give an algorithm for this problem?


What I've done so far:

I've tried to reduce the problem to the Generalized Assignment Problem (GAP). Let the cost $c_{ij}$ and the profit $p_{ij}$ for assigning worker $w_j$ to task $i$ be:

$c_{ij} = \begin{cases} 1, & w_j \in V_i \\ \infty, & w_j \notin V_i \\ \end{cases}$

$p_{ij} = 1$

The maximal capacity $C_i$ for each task is $s_i$. This should work as long as there is an assignment with the optimal distrubution ($d = 0$). Otherwise some workers remain unassigned.

Let $V_i^{'}$ be the set of workers suitable only for task $i$, then $|V_i^{'}| \le |X_i| \le |V_i|$. We could set every $C_i$ to a value within these bounds, such that $\sum_{i=1}^m C_i = n$, order all possiblities ascending by the resulting $d$ and solve each GAP until there is a solution with all workers assigned. This seems however inefficient to me (does it even work?).

$\endgroup$
1
$\begingroup$

Try to define a flow-Network in the following way:

$\{s,t\}\cup W \cup V$ are the vertices. and $E = \{(s,w) | w\in W\} \cup \{(w,v) | w \text{ is suitable to do } v\} \cup \{(v,t) | v\in V\}$ are the edges with capacity one for each $(w,v)$ edge and $(s,w)$ and the capacity of the $(v,t)$ edges is first set to $s_v$ then just iterate over sizes of $s_v$'s and every time use min-flow algorithm.

that should probably work.

$\endgroup$
  • $\begingroup$ Could you elaborate "iterate over sizes of $s_v$s"? $\endgroup$ – Simon S May 17 '14 at 23:23
  • $\begingroup$ yes, first set all of them to $s_i$ and then to $s_i+1$ untill they all reach maximum of $n$ just try all the option, and just check for each option the "cost" you get $\endgroup$ – Snufsan May 18 '14 at 9:35
  • $\begingroup$ So to be sure i understand it correctly, for $n=m=3$, $s=(0,1,2)$ the iterations would be $(0,1,2), (1,2,3), (2,3,3),(3,3,3)$. Im not entirely sure how this guarantees minimality, but i ran some positive tests. Thanks! $\endgroup$ – Simon S May 18 '14 at 12:44

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.