The Housing Office at Georgia Tech has to deal with a big problem every fall; how to make dormitory assignments so as to leave everybody reasonably happy. Of course, it may not be possible for everybody to be actually "happy" with their roommate assignment, so Housing's true aim would probably be to at least minimize the amount of misery created overall with the assignments.

Here's the thing...suppose that for Fall 2006, a total of 1964 freshmen are planning to live on campus in a dorm. Each student has, as part of their enrollment information, submitted a "wish list" regarding their preferences in terms of a roommate. These include such things as serious study habits, from Alabama, not from Alabama, likes jazz, talkative, no pet snakes, etc. Some of these attributes may have higher priorities than others, so Housing may "weight" them in some way.

In any event, what Housing would like to do is find a pairing of individuals that, in some sense, maximizes total "acceptability" and for which there is enough dorm space. For example, if two rooms are available for four students, but one student is absolutely unacceptable to the other three (under any circumstance), then two rooms will simply not suffice. Nonetheless, what do you think about the problem? Is it tricky? Does it get easier or harder if rather than pairs, Housing is looking for groups of three (i.e. for dorms with 3-person suites)?