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:
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.