A variant of the Assignment Problem

Question

In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task needs to be assigned to exactly $m$ or $m+1$ agents.

It is guaranteed this this is possible: the segment $\left[ |A|n, |A|(n+1) \right]$ intersects the segment $\left[ |B|m, |B|(m+1) \right]$.

Each agent-task combination yields a profit, and I want to maximize the profit.

Is this a special case of one of the known problems? How can this be solved? If not practical for n=100,000, what are good approximations and what is their complexity?

_{Not a comp.scientist, but have done the basic research. Please excuse me if I've overlooked anything obvious.}

Answer 1

This can be formulated as an instance of min-cost (or in this case, max-profit) flow.

Set up a network as follows. There will be four layers.

The first layer is a single node we call the source. The next layer consists of a node for each agent. The next layer has a node for each task. The final layer is one node we call the sink. For each edge, we give a capacity and a profit. The min-cost flow algorithm can be used to find the flow through this graph that produces the greatest profit.

For each agent, we create two edges connecting the source to that agent, one having capacity $n$ and large profit; the other having capacity 1 and profit 0.

We connect each task to the sink with two edges, one having capacity $m$ and large profit; the other having capacity 1 and profit 0.

We connect every agent to every task, with an edge having capacity 1 and profit given by the agent-task combination.

We now use a min-cost flow algorithm to find the optimum flow. Because the min-cost flow problem has an integrality property, the flow on each agent-task edge will either be 0 or 1. This gives the assignment of the agents to their tasks.

Because the profit on the source-agent edges with capacity $n$ is large, the optimal solution will always use these, ensuring that every agent has at least $n$ tasks. Because the other source-agent edge has capacity 1 (and profit 0), each agent can have at most $n+1$ tasks. Similarly, each task is assigned to either $m$ or $m+1$ agents.

The min-cost flow algorithm won't be practical if each agent needs $100,000$ tasks, though. Is that really what you meant by $n=100,000$? How many tasks and how many agents?

Answer 2

(Partial answer/Too long for comment) Note that if $|T| \neq |A|$, we can introduce dummy tasks or agents carrying zero profit, and make the cardinalities equal. Let $t_d,a_d$ be respectively the number of dummy tasks and agents. Suppose now that the tasks are $T_1,\ldots T_s$ and the agents are $A_1,\ldots,A_s$. Let $\mathtt{assign}(T_i,A_j)$ be a boolean function which outputs $1$ iff $T_i$ is assigned to $A_j$ (and conversely). We need to maximize the profit:

$P = \sum_{i,j} \mathtt{assign}(T_i,A_j) \cdot \mathtt{profit}(T_i,A_j)$

where the $\mathtt{profit}$ matrix is known. The constraints on the agents and tasks imply:

$$ \forall j:\sum_{1\leq i \leq s} \mathtt{assign}(T_i,A_j) \in \{n+a_d,n+1+a_d\}; \\ \forall i:\sum_{1\leq j \leq s} \mathtt{assign} (T_i,A_j) \in \{m+t_d,m+1+t_d\} $$

This is equivalent to constraining the $\mathtt{assign}$ matrix to have row and column sums within those ranges. I take it that $m,n$ are arbitrary integers.

Clearly the problem is an integer programming problem , somewhat like the Matching or Job Assignment problem. My guess is that the constraints make the problem NP-hard. Approximations would involve replacing the above constraints with something like: $ \forall j: \sum_{1\leq i \leq s} \mathtt{assign}(T_i,A_j) \leq n+1+a_d$

and similarly for the $i$'s. HTH.