A QUBO Framework for Team Formation

Karan Vombatkere ✉, Theodoros Lappas, Evimaria Terzi · 2025

Read A QUBO Framework for Team Formation by Karan Vombatkere ✉, Theodoros Lappas, 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-23209.txt.

Introduction

Karan Vombatkere, Theodoros Lappas, and Evimaria Terzi present a 2025 frame that casts team building as one math form. The classic task picks experts to cover a job's skills at low cost, but each cost sense spawned its own solver. The team fold three cost senses into a single quadratic binary form, the kind quantum-style and graph solvers eat well. Two general solvers were put to the test.

QUBO-built teams matched or beat the set baselines. A graph neural net also learned expert and skill maps that carried to fresh tasks, a transfer trick. One form for many cost rules lets planners swap solvers freely. Hiring and project staffing tools could plug the frame in directly. The work is a bridge between combinatorics and learning.

Catalog record

CREATORKaran Vombatkere ✉, Theodoros Lappas, Evimaria Terzi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

A QUBO Framework for Team Formation Karan Vombatkere ✉, Theodoros Lappas, Evimaria Terzi Abstract The team formation problem assumes a set of experts and a task, where each expert has a set of skills and the task requires some skills. The objective is to find a set of experts that maximizes coverage of the required skills while simultaneously minimizing the costs associated with the experts. Different definitions of cost have traditionally led to distinct problem formulations and algorithmic solutions. We introduce the unified TeamFormation formulation that captures all cost definitions for team formation problems that balance task coverage and expert cost. Specifically, we formulate three TeamFormation variants with different cost functions using quadratic unconstrained binary optimization (QUBO), and we evaluate two distinct general-purpose solution methods. We show that solutions based on the QUBO formulations of TeamFormation problems are at least as good as those produced by established baselines. Furthermore, we show that QUBO-based solutions leveraging graph neural networks can effectively learn representations of experts and skills to enable transfer learning, allowing node embeddings from one problem instance to be efficiently applied to another. 1 Introduction The team formation problem is commonly defined as follows: given a set of experts, each possessing a set of skills, and a task that requires specific skills, the goal is to identify a subset of experts best suited to complete the task. A vibrant stream of literature has been dedicated to algorithmic solutions for addressing an ever-expanding universe of variants of this problem [ 1 , 2 , 13 , 16 , 18 , 24 , 34 , 35 ] . The fundamental requirements in most team formation problems is that the selected experts maximize the coverage of the required skills while minimizing their cost . Existing work on this problem combines these two requirements, by setting one as a constraint and the other as the objective. The cost of a team has many different definitions with each leading to a different problem formulation. Common cost functions include a linear sum of individual expert costs or a network-based cost that accounts for the structural connectivity of the selected experts within an underlying social graph. Inspired by recent work [ 25 , 34 ] , we integrate both the coverage and cost objectives aiming to find a team \mathbf{x} for task J such that \lambda Cov(J\mid\mathbf{x})-Cost(\mathbf{x}) is maximized. We call this general problem TeamFormation . In this formulation, \lambda is a normalization factor that balances the two components of the objective. This formulation is general and can incorporate direct costs associated with experts or more complex cost functions, e.g., coordination costs. In this paper, we examine three variants of the TeamFormation problem resulting from different cost functions, and show that they can be expressed as quadratic unconstrained binary optimization (QUBO) problems. This perspective enables us to frame team formation as an energy minimization problem, drawing parallels with physics-based combinatorial optimization techniques. Figure 1 : High-level flowchart of our QUBO framework for TeamFormation . We explore two classes of solution methods: one using QUBO solvers [ 12 ] and another leveraging graph neural networks (GNNs) [ 29 ] . QUBO solvers provide exact or near-optimal solutions. However, they operate as black-box solvers that do not provide any insight into the underlying space of experts and skills, and their computational complexity grows significantly with problem size. Motivated by these limitations, and inspired by recent work on deep learning for combinatorial optimization problems [ 6 , 30 ] , we introduce a GNN-based approach. This approach models the problem as an unsupervised node classification task; the classification process assigns each expert a binary decision (selected or not selected in the team) and the GNN learns to classify the experts by optimizing a QUBO-based loss function that corresponds to maximizing the TeamFormation objective. Apart from learning good solutions, the embeddings learned by the GNN provide a semantic representation of the expert-skill space, where node proximity reflects relationships between skills and experts. To the best of our knowledge, we are the first to provide a unified QUBO-based framework (see Fig. 1 ) for team formation, enabling a consistent algorithmic approach across different TeamFormation variants. In our experimental evaluation, we utilize real-world datasets from diverse domains, including collaboration networks of artists and scientists, and online labor market data. Our results demonstrate that our general algorithms consistently find high-quality solutions, often outperforming combinatorial baselines designed specifically for certain problem variants. Furthermore, our experiments highlight the potential for transfer learning, where GNNs trained on one problem instance can be effectively used to solve related instances with minimal additional computation. 2 Related Work Our QUBO-based formulation for the TeamFormation problem applies to all variants requiring a balance between coverage and cost. In this way, our work generalizes a lot of existing work on team formation, relates to work on balancing submodular objectives with other objective functions, and extends ideas from QUBO combinatorial optimization and deep learning. Algorithmic Team Formation. Early work in team formation focused on algorithmic methods to select experts to collectively cover all the skills required by a single task, while collaborating effectively within a social network [ 16 , 18 ] . Related work considered forming multiple teams of experts to cover the skills of multiple tasks while bounding the workload or coordination cost across experts [ 1 , 2 ] . Follow-up works then considered more flexible problem variations that aim to balance partial task coverage with expert cost, maximum workload, and coordination cost. These works primarily employ established algorithmic methods, such as integer programming and greedy heuristics [ 24 , 25 , 34 , 35 ] . More recent literature has expanded beyond such methods to leverage deep learning for various team-formation variants. For instance, deep neural networks have been used to recommend new teammates to optimally compose high-performance teams [ 8 , 28 ] . In another relevant example, a variational bayesian neural architecture was used to learn representations for teams whose members have collaborated in the past, enabling the selection of top- k teams of experts that collectively cover a set of skills [ 13 ] . Our TeamFormation formulation generalizes several prior formulations by incorporating task coverage and a flexible cost definition into a single objective. Furthermore, our GNN-based method is distinct from the deep learning methods used in prior work. Submodular Maximization. The coverage function is monotone and submodular, which is useful within discrete objective functions, as it encodes a natural diminishing returns property and also comes with an extensive literature on optimization techniques [ 9 , 10 , 17 ] . The greedy algorithm achieves a 1-1/e approximation for maximizing a nonnegative monotone submodular function subject to a cardinality constraint [ 23 ] . There is also work involving maximizing submodular minus modular or linear functions, where no multiplicative approximation guarantees are possible in polynomial time due to potential negativity [ 14 , 15 ] . The Cov() function in our TeamFormation objective is nonnegative monotone submodular, and depending on the definition of Cost() used, variants of our general problem relate to balancing submodular and other functions. However, our solution framework is general and it does not rely on the fact that our functions have

Read the complete text