  The rise of online labor markets (e.g., Freelancer, Guru and Upwork) has
ignited a lot of research on team formation, where experts acquiring different
skills form teams to complete tasks. The core idea in this line of work has
been the strict requirement that the team of experts assigned to complete a
given task should contain a superset of the skills required by the task.
However, in many applications the required skills are often a wishlist of the
entity that posts the task and not all of the skills are absolutely necessary.
Thus, in our setting we relax the complete coverage requirement and we allow
for tasks to be partially covered by the formed teams, assuming that the
quality of task completion is proportional to the fraction of covered skills
per task. At the same time, we assume that when multiple tasks need to be
performed, the less the load of an expert the better the performance. We
combine these two high-level objectives into one and define the BalancedTA
problem. We also consider a generalization of this problem where each task
consists of required and optional skills. In this setting, our objective is the
same under the constraint that all required skills should be covered. From the
technical point of view, we show that the BalancedTA problem (and its variant)
is NP-hard and design efficient heuristics for solving it in practice. Using
real datasets from three online market places, Freelancer, Guru and Upwork we
demonstrate the efficiency of our methods and the practical utility of our
framework.
