5
$\begingroup$

I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given the expertise of the worker for the job $\omega(w,j)$. The goal is to select a subset of jobs $S\subseteq J$ and assign exactly two workers to each job $j \in S$ while maximizing the total expertise.

That is, if $x_{w, j} = 1$ indicates that the worker $w$ has been assigned to job $j$, solve the following program:

$$ maximize \sum_{j \in S} x_{w, j} \cdot \omega(w, j) $$ s.t. $$ \sum_{j\in S} x_{w, j} \leq 1, \forall w\in W $$ $$ \sum_{w\in W} x_{w, j} = 2, \forall j \in S $$ $$ x_{w, j} \in \{0, 1\} $$

Edit:

It seems like my explanation is not very clear so I am adding a simple example. Consider the following graph where dotted edges have weight 0 and solid edges have weight 1. Worker $i$ has expertise $1$ in job $i$ and expertise $0$ in the other job.

The two possible solutions both have value 1: either assign both workers to job 1, or assign both workers to job 2. Observe that assigning worker 1 to job 1 and worker 2 to job 2 would result in a solution of value 2, but it is not a valid solution since a job must be assigned exactly 2 workers.

enter image description here

$\endgroup$
  • 5
    $\begingroup$ What exactly is the question? If there is a solution to the problem? Your point is not clear. $\endgroup$ – Konstantinos Koiliaris Jul 1 '15 at 16:54
  • 1
    $\begingroup$ Well for one thing this is of course a case of 0-1 Integer Programming and thus some classical algorithms and heuristics such as branch and bound + cutting planes can be applied $\endgroup$ – frogeyedpeas Jul 1 '15 at 19:35
  • 1
    $\begingroup$ But none of those techniques are specific to this problem $\endgroup$ – frogeyedpeas Jul 1 '15 at 19:35
  • 2
    $\begingroup$ It's a min cost flow problem, so it can be solved for instance by the network simplex method. The network is a complete bipartite graph with arcs from workers to jobs. Every worker node has supply 1 and every job node has demand 2, and the cost of arc $(w,j)$ is $-\omega(w,j)$. $\endgroup$ – Thomas Kalinowski Jul 2 '15 at 2:29
  • 2
    $\begingroup$ Thanks. I've overlooked the restriction to $S$. Anyway, you get a 0-1-program by replacing the right hand side of the equality constraints by $2y_j$ with a binary $y_j$ for every $j\in J$. $\endgroup$ – Thomas Kalinowski Jul 2 '15 at 6:36
3
$\begingroup$

This problem is a special case of the b-matching problem, and hence can be solved in polynomial time. Extensive information on b-matchings can be found for instance in the book:

László Lovász and Michael D. Plummer:
Matching Theory
ISBN-10: 0-8218-4759-7
ISBN-13: 978-0-8218-4759-6

$\endgroup$
  • $\begingroup$ to my understanding, b-matching is placing only an upper bound on the number of edges that can be connected to one vertex. However, in this problem the number of edges connected to a job has to be either 0 or 2. $\endgroup$ – George Octavian Rabanca Jul 2 '15 at 17:26
  • $\begingroup$ Note that the problem becomes NP-complete if every job needs 3 workers (reduction from exact cover by 3-sets). $\endgroup$ – Thomas Kalinowski Jul 3 '15 at 3:11
  • $\begingroup$ @George Octavian Rabanca: Did you even care to look into the book by Lovasz and Plummer? On page 389, they explain how most of the b-matching theory carries over to the case of so-called "one-element gaps". Your case is centered around the interval 0,1,2 (feasible degrees), but there is a gap of one integer in the middle (removing 1) and just leaving 0,2. $\endgroup$ – Gamow Jul 3 '15 at 8:45
  • $\begingroup$ @Gamow: Thanks. Yes, the problem I am proposing fits the one-element gap scenario, but the authors don't discuss the weighted setting in relation to f-factors. It is easy to see that the reductions they present hold true when the graph is weighted, but the reduction of the "one-element gap" case is not presented and it's not clear that in weighted graphs we'd obtain a maximum weight f-factor. I will have to find the original papers on that. $\endgroup$ – George Octavian Rabanca Jul 3 '15 at 22:14
  • $\begingroup$ @Gamow: It seems like the weighted version of the f-factor problem with one element gaps has not been solved at least by 1995. Pulleyblank says in his 1995 survey "Matchings and Extensions" that: "Recently Cornuejols(1988) ... [solved] this problem when no gap of size greater than one is permitted. However, the corresponding weighted problem has not yet been solved." (p. 212 of "Handbook of combinatorics" vol. 1) Has this problem been solved since? $\endgroup$ – George Octavian Rabanca Jul 6 '15 at 15:50

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.