Forming Coordinated Teams that Balance Task Coverage and Expert Workload

Karan Vombatkere, Aristides Gionis, Evimaria Terzi · 2025

Read Forming Coordinated Teams that Balance Task Coverage and Expert Workload by Karan Vombatkere, Aristides Gionis, Evimaria Terzi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05898.txt.

Introduction

Karan Vombatkere and co-authors formulate a team-building problem that balances skill coverage against expert workload. Their 2025 paper starts from staffing tasks that each need several skills. Classic versions demand full coverage of every task, which can overload a few popular experts.

Their version scores coverage and the heaviest workload together in one objective, accepting partial coverage to keep loads fair. They prove the problem is hard in the formal sense. A variant adds a coordination graph, requiring each team to sit within a bounded distance so members work well together. The team give a template algorithm with provable guarantees for the base problem, plus speedups that scale it to large data. The framing suits consulting firms and hospitals that staff many projects from one expert pool.

Catalog record

CREATORKaran Vombatkere, Aristides Gionis, Evimaria Terzi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-05898

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Forming Coordinated Teams that Balance Task Coverage and Expert Workload Karan Vombatkere, Aristides Gionis, Evimaria Terzi Abstract We study a new formulation of the team-formation problem, where the goal is to form teams to work on a given set of tasks requiring different skills. Deviating from the classic problem setting where one is asking to cover all skills of each given task, we aim to cover as many skills as possible while also trying to minimize the maximum workload among the experts. We do this by combining penalization terms for the coverage and load constraints into one objective. We call the corresponding assignment problem Balanced-Coverage , and show that it is 𝐍𝐏 \mathbf{NP} -hard. We also consider a variant of this problem, where the experts are organized into a graph, which encodes how well they work together. Utilizing such a coordination graph, we aim to find teams to assign to tasks such that each team’s radius does not exceed a given threshold. We refer to this problem as Network-Balanced-Coverage . We develop a generic template algorithm for approximating both problems in polynomial time, and we show that our template algorithm for Balanced-Coverage has provable guarantees. We describe a set of computational speedups that we can apply to our algorithms and make them scale for reasonably large datasets. From the practical point of view, we demonstrate how to efficiently tune the two parts of the objective and tailor their importance to a particular application. Our experiments with a variety of real-world datasets demonstrate the utility of our problem formulation as well as the efficiency of our algorithms in practice. keywords team formation, submodular optimization, greedy, social network, data mining algorithms 1 Introduction The abundance of online and offline labor markets (e.g., Guru, Freelancer, online scientific collaborations, etc.) has motivated a lot of work on the team-formation problem. In the team-formation setting, the input consists of ( i ) a task, or a collection of tasks, so that each task requires a set of skills, and ( ii ) a set of experts, where each expert is also associated with a set of skills. The objective is to identify one team, or one team for every task, such that all the skills in every task are covered by at least one team member. Notably, the majority of works in team-formation research require complete coverage of the skills of the input tasks ( Anagnostopoulos et al. 2010 ; Anagnostopoulos et al. 2012 ; Anagnostopoulos et al. 2018 ; Bhowmik et al. 2014 ; Kargar et al. 2013 ; Kargar and An 2011 ; Kargar et al. 2012 ; Lappas et al. 2009 ; Majumder et al. 2012 ; Li et al. 2015a ; Li et al. 2015b ; Li et al. 2017 ; Rangapuram et al. 2013 ; Yin et al. 2018 ) . The differences among existing papers lie in the way they define the “goodness” of a team. For example, in some cases they optimize the communication cost of the team, while in other cases they optimize the load of the experts, or their associated cost. We motivate the inherent trade off between task coverage and expert workload using the example of Fig. 1 . Consider the bipartite graph with experts as one set of nodes and tasks as the other. The edges shown in the graph represent the expert-task assignments. The assignment on the left, achieves 100% coverage for all three tasks; however Charlie has a workload of 3, Bob and David each have workload of 2 while Alice is not assigned to any task. However, the assignment on the right – which allows for partial coverage – does not cover any task 100%, yet it is more balanced in terms of expert workload; all experts now have a workload of 1. (a) Assignment with full coverage for all tasks and unbalanced expert workload. (b) Assignment with partial coverage and balanced expert workload. Figure 1 : Motivating example with 4 experts and 3 tasks. In this paper, we propose team-formation problems where the goal is to assign experts to a set of input tasks such that the task coverage is maximized, and at the same time, the maximum workload among the experts used is minimized. This trade-off suggests that we need not always cover the skills of every task completely, since covering a large fraction of their required skills might be sufficient. Also, given that overworked experts do not perform well, we penalize expert overloading by minimizing the maximum number of tasks assigned to an expert. Therefore, for an assignment A of experts to tasks, our goal is to maximize the combined objective: F(A)=\lambda C(A)-L_{\max}(A), (1) where C(A) is the sum of the fraction of the skills of the tasks being covered by their assigned experts and L_{\max}(A) is the maximum number of tasks assigned to a single expert. Although we normalize the two terms of the objective (Eq. ( 1 )) and make them comparable, in certain applications we may want to aim for different trade off between the coverage and maximum-load terms. Thus, we incorporate the balancing coefficient \lambda , which enables an effective tuning of the importance of the two terms. We call this problem Balanced-Coverage . Often, the experts are organized in a network, which encodes how well experts can work with each other. In the presence of such information, we extend the Balanced-Coverage problem so that the teams assigned to tasks have the property that their radius is not larger than a pre-specified threshold. The motivation is for teams to have small coordination cost and be able to work well with each other. We call this version of the problem Network-Balanced-Coverage . We show that the two problems we define, Balanced-Coverage and Network-Balanced-Coverage , are \mathbf{NP} -hard. From the application point of view, it makes sense to relax the hard constraint of full coverage; in practice, skills in tasks are often overlapping. For example, consider a task requiring skills: advertising, internet advertising, Facebook advertising, online marketing, social network platforms . Clearly, these are overlapping and not all of them need to be covered. Additionally, minimizing the maximum expert workload is desirable for better team performance. From the algorithmic point of view, optimizing the above objective, with or without the radius constraint in the teams, is challenging; the function itself may take negative values. Therefore, it does not admit multiplicative approximation guarantees. Although the coverage part of the objective ( C(\cdot) ) is a monotone submodular function, the maximum load part does not have a predictable form (i.e., it is not linear or convex). Therefore, recent techniques ( Harshaw et al. 2019 ; Mitra et al. 2021 ) on submodularity optimization cannot be applied. However, we adopt from these works a weaker notion of approximation and aim to find an assignment A such that: \lambda C(A)-L_{\max}(A)\geq\alpha\left(\lambda C(\mathit{OPT})\right)-L_{\max}(\mathit{OPT}), (2) where \mathit{OPT} is the optimal solution to the Balanced-Coverage or the Network-Balanced-Coverage problems. In this case, \alpha\leq 1 is an approximation guarantee that better fits functions like ours. In this paper, we show that for the Balanced-Coverage problem, we can design a polynomial-time algorithm with \alpha=\left(1-1/e\right) , which is probably the best we can hope for our objective

Read the complete text