Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
See this similar problem. –  Nicholas Mancuso Oct 20 '12 at 15:26
    
Question: if you have two tasks and two agents, and $n$ and $m$ are 1, you can either assign one task to each agent, or both tasks to both agents. Are your profits in this case $v_{1,1} + v_{2,2}$ and $v_{1,1}+v_{1,2} + v_{2,1} + v_{2,2}$, respectively? Or does the fact that each agent is doing two tasks reduce the total profit because they have to divide their time between the tasks? –  Peter Shor Oct 21 '12 at 11:12
    
The profits would be $v_{1,1}+v_{1,2}+v_{2,1}+v_{2,2}$. That is: profits are strictly cumulative and are not reduced if agents do more tasks. Why? –  Nitzan Shaked Oct 21 '12 at 15:23
    
@Nitzan: Why? It makes a difference in whether you can use the mincost flow algorithm to solve the problem. –  Peter Shor Oct 22 '12 at 14:26
add comment

2 Answers 2

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?

share|improve this answer
    
I meant there are ~100K agents. Each agent can do any of the tasks, but the number of tasks-per-agent is 5 or 6 in my case. –  Nitzan Shaked Oct 21 '12 at 15:16
    
Nice, but are the polynomial-time algorithms for solving this? –  Nitzan Shaked Oct 21 '12 at 15:24
    
There are lots of practical polynomial-time algorithms for solving min-cost flow (it's a special case of linear programming). See this paper. However, the algorithms are generally quadratic or worse, so it may be that they're too slow on this large a problem (maybe not ... they might actually run a lot faster than their worse-case running time) unless you can use some heuristic to trim all but the most profitable agent-task edges. –  Peter Shor Oct 21 '12 at 15:59
    
To complete my original question, then: what are known approx. algorithms for this? –  Nitzan Shaked Oct 22 '12 at 14:38
    
I seem to be missing something: what flow am I aiming for when solving for min-cost (or max-profit) flow? I should be aiming for the minimum cost of all max-flows, no? –  Nitzan Shaked Oct 22 '12 at 15:40
show 3 more comments

(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.

share|improve this answer
    
Thanks for the post. I should written earlier, I suppose, that I have already formulated this as a LP. The questions are whether this is indeed NP-hard, and if so what's a good estimation and its complexity. –  Nitzan Shaked Oct 21 '12 at 8:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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