5
$\begingroup$

I have this simple 'assignment' problem:

We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike the general assignment formulation in Wikipedia, a task $t_c$ can only be assigned to an agent based on the task's preferred agents $ta_c \subseteq A$. For example, if we have $ta_1= \{a_1, a_3\}$, that means that task $t_1$ can only be assigned to either agents $a_1$ or $a_3$. Now, each agent $t_d$ has a quota $q_d$ where $q_d$ is positive integer. This means that $a_d$ must be assigned with $q_d$ number of tasks.

The Problem

Given above and a set of quota $\{q_1, q_2, \dotso, q_n\}$, is there an assignment of tasks to agents such that all agents meet their respective quota $q$. Note that it is not necessarily that all tasks be assigned to an agent.

Possible Solution

I have tried reformulating this problem in terms of a bipartite graph $G(A, T, E = \cup ta_c)$ and expressed as a form of matching problem where given a matching $M$, a vertex agent $a_d\in A$ is matched up to $q_d$ times or is incident to $q_d$ edges in $M$ but the vertices in $T$ is incident to only one edge in $M$. Not really like the usual matching problem which requires that the edges in $M$ are pairwise non-adjacent.

However, it was suggested by someone (from cstheory, he knows who he is) that I could actually work this out as a maximum matching problem, by replicating an agent $a_d$ into $q_d$ vertices and 'conceptually' treat them as different vertices as input to the matching algorithm. The set of edges $E$ is also modified accordingly. Call the modified graph as $G'$

It is possible to have more than 1 maximum matchings from graph $G'$. Now, if I understand this correctly, I still have to check each of the resulting maximum matchings and see that at least one of them satisfies the $qouta$ constraint of each $agent$ to actually provide the solution to the problem.

Now, I want to prove that not finding one maximum matching $M$ $\in$ set of all maximum matchings of the graph $G'$ that satisfies the $qouta$ constraint of the problem guarantees that there really exists no solution to the problem instance, otherwise a solution exist which is $M$.

I want to show that this algorithm always give correct result.

Question

Can you share to me some intuition on how I might go to show this?

$\endgroup$
3
$\begingroup$

As I stated on the CSTheory post, this is solved via maximum matching. The following should give enough intuition to show that each agent $a_i$ has a $q_i$-matching iff a transformed graph $G'$ has a matching. First, construct the graph $G$. Now, for each agent $a_i$ and quota $q_i$, make a new graph $G'$ that has $q_i$ copies of $a_i$. That is to say, if agent $a_i$ has quota $q_i = 3$, make 2 new nodes $a_i', a_i''$ that have the same tasks as $a_0$.

Here is an illustration to help. Supposed we have the complete bipartite graph $K_{2,3}$ where agent $q_1 = 2, q_2 = 1$.

Original graph $G$, and modified graph $G'$:

Original graph G Modified graph G'

We see that agent $a_1$ has two copies in the new graph $G'$, while agent $a_2$ maintains just his lone copy. Solving for the maximum matching in $G'$ and then merging all copies of an agent to the original and you will have your best possible assignment. Since the edges are unweighted, one possible solution is (and merged solution):

Matching MFinal merged solution

$\endgroup$
  • $\begingroup$ hi again nicholas. Thank you for the suggestion! But I'm past that, and I'm asking a different question now. :) As I understand my problem, a maximum matching of $G$ is only a possible solution to it. I still have to check that a maximum matching satisfies the $qouta$ constraint of the problem. I hope this requirement of the problem looks clear to you. It's more of a decision problem, which asks whether a matching $M$ exists on $G$ such that each $a_d\in A$ (or in your suggested formulation, all vertex $a_d$ copies)is incident on a edge in $M$. $\endgroup$ – ultrajohn Sep 22 '12 at 23:48
  • 1
    $\begingroup$ I understand. Start by proving that if $G'$ has a matching, then quota is satisfied. Then prove if quota is satisfied then there exists a matching in $G'$. All the transformation-work has been done. Use that as the logical foundation. $\endgroup$ – Nicholas Mancuso Sep 22 '12 at 23:52
  • $\begingroup$ So if you remember, you answered a question I posted earlier about size of the maximum matching $M$ of $G'$. You said, that $|M|$ is not necessarily equal to $\min(|A|,|T|)$. For my problem, a solution exists if and only if a maximum matching M exists such that $|M| = \sum_{i=1}^{n} q_i$. Oh I think I just found out the answer to my question. :) $\endgroup$ – ultrajohn Sep 22 '12 at 23:53
  • 1
    $\begingroup$ Yes, but remember $M$ must be in $G'$, not in $G$. $\endgroup$ – Nicholas Mancuso Sep 22 '12 at 23:54
  • $\begingroup$ Yes, sorry for the mixed up. I think i know how to prove that now. Thank you really! $\endgroup$ – ultrajohn Sep 22 '12 at 23:57

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.