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$
9
  • 5
    $\begingroup$ What exactly is the question? If there is a solution to the problem? Your point is not clear. $\endgroup$ Jul 1, 2015 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$ Jul 1, 2015 at 19:35
  • 1
    $\begingroup$ But none of those techniques are specific to this problem $\endgroup$ Jul 1, 2015 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$ Jul 2, 2015 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$ Jul 2, 2015 at 6:36

1 Answer 1

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$
6
  • $\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$ Jul 2, 2015 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$ Jul 3, 2015 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, 2015 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$ Jul 3, 2015 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$ Jul 6, 2015 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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