1
$\begingroup$

I'm looking at a problem similar to an assignment problem.

There are both agents and tasks. Each agent has a list of tasks they are able to do, and cannot do any task not within that list (note that agents do not have a preference for what task they do, only a list of tasks they are able to do). A task can be assigned to multiple agents. However, the amount of agents assigned to a task must lie between a given minimum and maximum. A task could also be assigned to no agents. The goal is to maximize the amount of agents that are assigned to a task.

I've simplified the problem down to creating a bipartite graph with agents on one side and tasks on the other. An edge would be drawn between an agent and the tasks they are willing to do. The goal would be to take a subset of these edges that would have at most one edge from each agent node and a number of edges either at 0 or between the min/max for the task nodes.

I've thought it over, and I've got part of a possible solution. For each task node, they will be duplicated until they are at the same number as the maximum agents allowed to be on one task. Then a maximal matching could be found for that graph. After the matching is found, the duplicated nodes are all combined into one node. The problem with this is that I'm not sure how to enforce the condition that each task must have a minimum number of agents assigned to it. Ideally, we'd want to minimize the amount of tasks that are below the minimum but still have at least 1 agent. What approach should I take to enforce this goal of minimizing the tasks with an agent count between 1 and the minimum?

More progress has been made: a circular flow network almost works. The problem is my problem allows for a task to either be assigned (to at least the required minimum of agents) or be scraped (and assigned to no agents). The minimum of each edge in a circular flow network would enforce the required minimum, but make it so tasks couldn't be scraped. Any ideas how to address this?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The problem is $\mathsf{NP}$-hard via a reduction from Exact Cover by 3-sets problem. Let $(X,F)$ be an instance of Exact Cover by 3-sets problem. Then, the set $X$ corresponds to agents and the set $F$ corresponds to tasks. Each task will have an upper and lower bound of $3$. You can easily prove the following statement:

There exists a feasible solution to $(X,F)$ if and only if the maximum number of assigned agents are $|X|$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I've just found out about the circulation problem, however, there seems to be one issue. I can establish a lower bound in circulation problem, but that won't allow for a flow of 0, which is allowed in my problem (either the lower bound must be met for agents to work on it or the task gets scraped). $\endgroup$
    – Kevin Xia
    Commented May 6, 2022 at 21:01
  • $\begingroup$ @KevinXia That is a good point. Can you add this point in your question. $\endgroup$
    – Inuyasha Yagami
    Commented May 6, 2022 at 21:02
  • $\begingroup$ @KevinXia Can you check the answer again? $\endgroup$
    – Inuyasha Yagami
    Commented May 6, 2022 at 21:15
  • $\begingroup$ I apologize, but I'm not sure where this takes us. From what I can gather, this seems to determine whether a feasible result exists. However, the problem I have wants an actual matching between the agents and tasks. And if there isn't a perfect one that involves every agent, then the one that involves the most agents possible should be found. $\endgroup$
    – Kevin Xia
    Commented May 6, 2022 at 21:24
  • $\begingroup$ @KevinXia Yeah. You are right. We are looking for a matching with most agents possible only. If the most agents are exactly $|X|$ then there is a feasible solution to $(X,F)$. if most agents are less than $|X|$ then there is no feasible solution to $(X,F)$. You get it now? $\endgroup$
    – Inuyasha Yagami
    Commented May 6, 2022 at 21:26

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.