Often I find that people have the opinion that the class of NP-complete problems, as discussed in my previous post, in general, don’t show up in practice. And if they do show up, then they normally represent a restriction on the problem that we can solve easily. This line of thought though is unfortunately untrue 🙁 .
An example of a problem that has significant practical consequences, yet is NP-hard, is that of finding a maximum size stable matching in the context of what is known as the Hospital/Residents problem with ties.
In the Hospital/Residents problem (HR), we seek to assign a set of student doctors (residents) to hospital posts (a hospital may offer more than one post) – this task is carried out in many countries in a student’s first year after graduating from medical school. Each student is asked to rank a set of hospitals in strict preference order, with the hospitals ranking the set of students also by preference. However, in many schemes, hospital’s preference lists are allowed to contain ties. That is, a hospital is allowed to be indifferent between a set of students – this generally produces a more realistic set of preference lists, as otherwise the hospital may typically have to rank several thousand students individually. We note that this description of the problem is not complete but I’m describing a known practical situation here, not the general case of HR with ties, where a student’s preference list may also contain ties.
So what is a stable matching? A matching is stable in the context above if there is no student s that strictly prefers a hospital h to his current assignee h' (or s is unmatched), and h is either under-subscribed or prefers s to at least one assignee. I think an example will better illustrate:
students hospitals s: h h' h: s (t r) t: h h' h': r s t r: h h' |
The above states that student s prefers h to h', similarly for students t and r. For the hospitals, each is offering 1 post, and hospital h is indifferent between t and r and prefers s to both of them, with h' preferring r to s to t respectively. Now the matching {(t,h),(r,h')} is not stable. Why? Because s is unmatched and would rather be assigned to h than be unmatched, and h prefers s to t, so both s and h would get better off if h reject t and took on s. In this example a stable matching is {(s,h),(r,h')}.
Mmmmm maybe the last bit was a little complicated but I just wanted to give a feel for why we desire a matching to be stable.
As I mentioned earlier the problem of finding a maximum stable matching in this context is NP-hard. So why is this a problem? Well obviously we want to match as many students as possible, if not these people will not get a job, so this is very important to them. Also, clearly we want a matching to be stable for otherwise you end up with chaos as students and hospitals realise that they would be better off if they just switched. This is exactly what happened in the US prior to establishing a system (NRMP) that was based on stable matchings way back in the 50s.
However, despite its importance as a problem we are stuck! If we want to deal with ties (and also if we have no ties but “couples” who want to submit joint preference lists) we are in the realms of using heuristics. What this means is that we are highly unlikely to find a solution that maximises the number of students matched. This may not sound bad to you, but to those involved in the matching scheme, it could affect the rest of their life. That said, even a stable solution less than optimal size (it’s easy to find such a solution in polynomial-time) is more acceptable than a solution that is not stable.
Anyway, there you have it, a practical NP-hard problem. Also, there are many others. If this was of interest then I can maybe write up something about the Kidney Exchange Problem – this concerns the organisation of kidney transplants from live donors and it is known that the most important practical variants of this problem are NP-hard. This is in every sense of the word a life or death problem.