In this paper, we investigate the profit-aware team grouping problem in social networks. We consider a setting in which people possess different skills and compatibility among these individuals is captured by a social network. Here, we assume a collection of tasks, where each task requires a specific set of skills, and yields a different profit upon completion. Active and qualified individuals may collaborate with each other in the form of to accomplish a set of tasks. Our goal is to find a grouping method that maximizes the total profit of the tasks that these teams can complete. Any feasible grouping must satisfy the following three conditions: (i) each team possesses all skills required by the task, (ii) individuals within the same team are social compatible, and (iii) each individual is not overloaded. We refer to this as the problem. Our work presents a detailed analysis of the computational complexity of the problem, and propose a LP-based approximation algorithm to tackle it and its variants. Although we focus on team grouping in this paper, our results apply to a broad range of optimization problems that can be formulated as a cover decomposition problem.
To the best of our knowledge we are the first to formulate and study the team grouping problem and its variants. However, our work is closely related to other team formation and cluster hiring problems. @cite_0 introduce the minimum cost team formation problem. Given a set of skills that need to be covered and social network, their objective is to select a team of experts that can cover all required skills, while ensuring efficient communication between the team's members. There is a considerable amount of literature on this topic and its variants . In , they study cluster hire problem, where the objective is to hire a profit-maximizing team of experts with the ability to complete multiple projects, subject to a fixed budget. Different from all the above works where they aim to select a best qualified team, our objective is to group individuals into multiple teams. It turns out that these two problems are closely related, this allows us to leverage existing techniques for team formation to solve our problem.
@cite_0
2145604831
Given a task T, a pool of individuals X with different skills, and a social network G that captures the compatibility among these individuals, we study the problem of finding X, a subset of X, to perform the task. We call this the T EAM F ORMATION problem. We require that members of X' not only meet the skill requirements of the task, but can also work effectively together as a team. We measure effectiveness using the communication cost incurred by the subgraph in G that only involves X'. We study two variants of the problem for two different communication-cost functions, and show that both variants are NP-hard. We explore their connections with existing combinatorial problems and give novel algorithms for their solution. To the best of our knowledge, this is the first work to consider the T EAM F ORMATION problem in the presence of a social network of individuals. Experiments on the DBLP dataset show that our framework works well in practice and gives useful and intuitive results.