A self selecting team

Question

A team consisting of 100 members is to be assembled from a pool of 1000 applicants. Each applicant gets to pick the 99 other applicants he/she would like to have as teammates.

Each possible team gets a score that measures how well it satisfies the team mate preferences of its members. If Lisa is in a team and 11 of the people on Lisas wishlist are also in the team that team gets 11 points for Lisa. The points for all members are added up. The theoretical maximum any possible team can get is 99*100. The minimum is 0.

Now we want to find the team with the highest score. Trying to brute force this problem by computing the score for each possible combination (≈ 10^140) is not an option.

Is there a clever algorithm that will take a shortcut to the best answer or will one have to settle for an algorithm that finds a good answer?

Answer 1

I think that if you could solve this efficiently you could solve the http://en.wikipedia.org/wiki/Clique_problem efficiently - where there is a link between two nodes put each node on the list of the nodes that the other wants to work with. Looking at the article, I think you will find it hard to find even a guaranteed good approximation, unless your problem has some special structure to it.

Answer 2

You might try a hill climbing algorithm. Start with a member who is "popular" (picked most often by other members), and incrementally add new members who increase the team score the most. This is unfortunately not guaranteed to find the best solution, but it will probably find good ones. To improve your solution you could try simulated annealing.