Team Formation on Social Networks
Nihal Berktaş
Department of Industrial Engineering, Bilkent University

The success of a team depends on the quality of the communication among the team members as well as their technical capabilities. We study the Team Formation Problem (TFP) in which the quality of communication is taken into account using the proximity of the potential members in a social network. Given a set of required skills, TFP aims to construct a capable team that can communicate effectively. We study TFP with two measures for communication: sum of distances and diameter. We compare the quality of solutions using various performance measures. Our experiments indicate the following: First, considering only one type of cost may yield solutions that perform poorly in other performance measures. Second, the heuristics in the literature find solutions that are far from optimal whereas a general purpose solver is capable of solving small and medium size instances to optimality. To find solutions that perform well on several performance measures, we propose the diameter constrained TFP with sum of distances objective. To solve larger sizes, we propose a novel branch and bound approach: we formulate the problem as a constrained quadratic set covering problem, use the reformulation-linearization technique and relaxation to be able to decompose it into a series of linear set covering problems and impose the relaxed constraints through branching. Our computational experiments show that the algorithm is capable of solving large sizes that are intractable for the solver.

Short Bio
Nihal Berktaş is a PhD candidate in Department of Industrial Engineering at Bilkent University. She received her B.Sc. and M.Sc. degrees from the same department. Her current research interests focus on deterministic and stochastic discrete optimization and its applications.

Friday, March 8, 2019 at 4.00 pm in IE03


Announcement Category