At the heart of many successful social networks, from community organizations to cutting-edge tech startups, and spanning across schools, hospitals, and research institutions, are cohesive teams working towards common objectives. However, selecting individuals for such teams can present computational challenges.


Stepping up to address this challenge is Professor Dorit Hochbaum and her groundbreaking study, “A Breakpoints Based Method for the Maximum Diversity and Dispersion Problems.” Together with former students Zhihao Liu and Olivier Goldschmidt, Professor Hochbaum leverages her prior research to tackle the Maximum Diversity Problem (MDP) head-on, introducing a powerful new method known as the Breakpoints Algorithm.

The Maximum Diversity Problem (MDP) is an optimization challenge centered around selecting elements from a set to maximize their total pairwise utility. This concept finds diverse applications, including genetic engineering, transportation system management, and alternative energy solutions. Recently, there has been a growing interest in applying MDP principles to team formation within social networks, where it holds significant potential impact.

In her recent study, Hochbaum employs her Breakpoints algorithm to craft teams based on a meticulous evaluation of the utility derived from including pairs of individuals in a team. For instance, in one scenario, utility is assessed based on the pair’s history of collaboration, while in another, it reflects the heightened diversity brought about by their inclusion in the team.

Hochbaum’s primary focus lies in solving the Maximum Diversity Problem subject to a budget constraint on the size of the team, a challenge that has long perplexed researchers. By introducing an efficient frontier and breakpoints, Hochbaum pioneers a new approach to team formation. The efficient frontier delineates a range of optimal solutions, while breakpoints signify critical values where changes occur in optimal solutions. When the budget aligns with a breakpoint, an optimal solution is achieved. However, when they don’t align, Hochbaum devises a solution by merging the smaller budget breakpoint set with individuals from the larger set. This yields a solution encompassing individuals between the two sets. Additionally, the authors introduce techniques to increase the quantity and density of breakpoints around desired budget values. While not guaranteed to be optimal, this approach consistently outperforms existing methods in both solution quality and computational speed.

Hochbaum’s novel Breakpoints algorithm represents a significant advancement in optimizing team compositions, accounting for factors like skills, compatibility, and diversity. Beyond its application in team formation, the algorithm holds promise for solving problems involving diverse selections and streamlining complex computations in various domains.


This article originally appeared in the 2023 edition of Berkeley IEOR Magazine

Berkeley IEOR Magazine


Source

Hochbaum, D. S., Liu, Z., & Goldschmidt, O.. “A Breakpoints Based Method for the Maximum Diversity and Dispersion Problems.” SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23).