<p>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:</p>

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

CC BY-SA 3.0
2016-02-20T09:52:41.407Z
@GeorgeOctavianRabanca Your special case is much less involved and can be directly reduced to matching. Use the same idea in [this answer](http://cstheory.stackexchange.com/a/33859/314), but modify the weight instead (and try all possible even $k$).
Chao Xu
CC BY-SA 3.0
2015-07-02T17:26:06.907Z
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.
George Octavian Rabanca
CC BY-SA 3.0
2015-07-03T03:11:19.057Z
Note that the problem becomes NP-complete if every job needs 3 workers (reduction from exact cover by 3-sets).
Thomas Kalinowski
CC BY-SA 3.0
2015-07-03T08:45:21.473Z
@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.
Gamow
CC BY-SA 3.0
2015-07-03T22:14:41.050Z
@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.
George Octavian Rabanca
CC BY-SA 3.0
2015-07-06T15:50:19.213Z
@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?
George Octavian Rabanca
CC BY-SA 3.0
2015-07-02T08:07:37.140Z
2015-07-02T08:07:37.140Z
Gamow
<p>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 <strong>exactly two workers</strong> to each job $j \in S$ while maximizing the total expertise.  </p>

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

<p>$$
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\}
$$</p>

<p>Edit: </p>

<p>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.  </p>

<p>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.</p>

<p><img src="https://i.sstatic.net/3STvF.png" alt="enter image description here"></p>

CC BY-SA 3.0
2015-07-01T16:54:51.783Z
What exactly is the question? If there is a solution to the problem? Your point is not clear.
Konstantinos Koiliaris
CC BY-SA 3.0
2015-07-01T19:35:21.827Z
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
Sidharth Ghoshal
CC BY-SA 3.0
2015-07-01T19:35:36.060Z
But none of those techniques are specific to this problem
Sidharth Ghoshal
CC BY-SA 3.0
2015-07-02T02:29:45.623Z
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)$.
Thomas Kalinowski
CC BY-SA 3.0
2015-07-02T04:22:41.967Z
I am not actually sure this is an integer program because the set S must be decided before.  This is actually turns out to be the difficult part of the problem.
George Octavian Rabanca
CC BY-SA 3.0
2015-07-02T04:25:03.203Z
@KXK Yes, I am wondering if it is a known problem and if there is any known polynomial algorithm for this problem or if the problem is known to be NP-complete and there exists an approximation algorithm for it.
George Octavian Rabanca
CC BY-SA 3.0
2015-07-02T04:36:03.050Z
@thomas: this does not take into consideration that only some of the jobs in J (the ones in the subset S) are going to be assigned.  And moreover, they have to be assigned to exactly 2 workers.
George Octavian Rabanca
CC BY-SA 3.0
2015-07-02T06:36:54.870Z
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$.
Thomas Kalinowski
CC BY-SA 3.0
2015-07-02T18:27:19.957Z
@GeorgeOctavianRabanca You are right about the flow idea, it's not clear how to solve it with it. I removed the answer.
Konstantinos Koiliaris
<ds.algorithms><reference-request><matching><bipartite-graphs>
Assignment problem with multiple workers for each job
George Octavian Rabanca
# Assignment problem with multiple workers for each job

(Asked by: username_0 on 2015-07-01)

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](https://i.sstatic.net/3STvF.png)

**Tags:** ds.algorithms, reference-request, matching, bipartite-graphs
> **Comments:**
> **username_1**: What exactly is the question? If there is a solution to the problem? Your point is not clear.  
> **username_2**: 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  
> **username_2**: But none of those techniques are specific to this problem  
> **username_3**: 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)$.  
> **username_0**: I am not actually sure this is an integer program because the set S must be decided before.  This is actually turns out to be the difficult part of the problem.  
> **username_0**: @KXK Yes, I am wondering if it is a known problem and if there is any known polynomial algorithm for this problem or if the problem is known to be NP-complete and there exists an approximation algorithm for it.  
> **username_0**: @thomas: this does not take into consideration that only some of the jobs in J (the ones in the subset S) are going to be assigned.  And moreover, they have to be assigned to exactly 2 workers.  
> **username_3**: 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$.  
> **username_1**: @GeorgeOctavianRabanca You are right about the flow idea, it's not clear how to solve it with it. I removed the answer.  

---

## 1 answers

### Answer by username_4 on 2015-07-02. Score: 3 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_3**: Note that the problem becomes NP-complete if every job needs 3 workers (reduction from exact cover by 3-sets).  
> **username_4**: @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.  
> **username_0**: @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.  
> **username_0**: @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?  
> **username_5**: @GeorgeOctavianRabanca Your special case is much less involved and can be directly reduced to matching. Use the same idea in [this answer](http://cstheory.stackexchange.com/a/33859/314), but modify the weight instead (and try all possible even $k$).  

---

