document: Online team formation in social networks We study the problem of online team formation . We consider a setting in which people possess different skills and compatibility among potential team members is modeled by a social network . A sequence of tasks arrives in an online fashion , and each task requires a specific set of skills . The goal is to form a new team upon arrival of each task , so that ( i ) each team possesses all skills required by the task , ( ii ) each team has small communication overhead , and ( iii ) the workload of performing the tasks is balanced among people in the fairest possible way . We propose efficient algorithms that address all these requirements : our algorithms form teams that always satisfy the required skills , provide approximation guarantees with respect to team communication overhead , and they are online-competitive with respect to load balancing . Experiments performed on collaboration networks among film actors and scientists , confirm that our algorithms are successful at balancing these conflicting requirements . This is the first paper that simultaneously addresses all these aspects . Previous work has either focused on minimizing coordination for a single task or balancing the workload neglecting coordination costs .
doc_bio_tags: O B I O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O