This is an example of an NP-hard problem that surprisingly broadly applies to everyday situations, just like the bin-packing problem that has been on the front page recently. Do you know of other NP hard problems with surprising applicability to everyday situations?
One that I find very interesting is optimizing function layout in binaries to improve their compressibility [2], which is important for mobile apps.
[1] https://scholar.google.com/scholar?cites=1196492606453931313...
We worked on improvements to this following our reproducibility study including a synchronized iterative version and alternative estimation functions.
You can find the paper here if you're still interested!