Optimal hotel room pairing

The greedy hotel pairing algorithm from my previous post gives good solutions. If you make some fairly reasonable-sounding assumptions about the problem, very good solutions. At any rate nicer than forcing a human to drudge through it; both in terms of person-hours spent and quality of the solutions.

However, it turns out I was wrong about them being optimal solutions. There's no guarantee they would be, and in fact a good chance that they won't.

Finding optimal solutions

The good news is that there is a way to find the optimal solution. This problem can be modeled as a graph matching problem; what we're trying to find is a weighted maximal matching.

This is really easy if the graph is bipartite, but in our case we're actually dealing with two complete graphs: we try to pair people with similar gender. Within that compatible group, anyone can theoretically pair with anyone.

People interested in additional reading might be interested in:

• Notes from a Stanford course by Jan Vondrak
• Notes from an Inria course by Frederic Havet

Picking an algorithm

There are several feasible algorithms for this.

• Edmonds' blossom algorithm, the first polynomial-time algorithm with running time \(O(V^4)\) or \(O(V^2\cdot E)\)
• Gabow's 1973 PhD thesis, an \(O(V^3)\) algorithm
• An \(O(\sqrt{V} \cdot E)\)) improvement by Micali (yes, that Micali) and Vazirani
• Another improvement by Gabow, \(O(V(E + \log{V}))\)

The current state of the art in computerized algorithms appears to be Blossom V by Vladimir Kolmogorov. This algorithm finds perfect matchings (i.e. all nodes are included), which may be impossible for us, e.g. because of an odd number of pairs.

Issues

One issue with this approach is that it becomes pretty much impossible to adapt this to rooms for more than two people. In order to support that case my previous greedy algorithm remains the best thing I've found.

I was unable to find an implementation of this in Java or Clojure. Fortunately, there is a Python library called NetworkX that does have an implementation.

I have not yet turned this into a fully functional program, because:

• it's too late to apply it for this year
• there's a good chance we won't be doing this again for next year

Credits

I'd like to thank Tor Myklebust (tmyklebu on Freenode) for pointing out I was wrong, and shoving me in the direction of the answers.

In this blog post I used several freely available graph illustrations from Wikipedia. The complete graph illustrations were made by koko90.