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?).
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.