This dovetails into one of my favorite CS sub-fields: approximation algorithms. In many cases NP-Hard problems may be approximated with a guaranteed lower bound of accuracy. For example, solving the euclidean version of the travelling salesman problem using a minimum spanning tree finds solutions that are no worse than 1.5 times the true minimum length, and there are heuristics with weaker guarantees that consistently perform better in practice.

That is proximal to one of my peeves in this space: People who misunderstand approximation results to be meaningful when often they're not.

For example, the minimum set cover problem shows up in cases like "What minimal set of test vectors covers all the conditions in my code?". There is an obvious greedy algorithm: "Start with nothing, pick the vector that covers the most yet-uncovered cases, repeat until all are covered".

There is an approximation result that says no polynomial time algorithm can do more than a small factor better than this greedy algorithm.

But this is a _worst case_ result, and absolutely useless for any problem you will encounter in practice.

It's trivial to come up with ways of improving the greedy algorithm: First off the simple greedy algorithm will often produce output which has completely redundant elements that can just be removed, because some collection of later added items that were necessary to cover some rare cases completely cover some earlier added item. Adding a simple postprocess to remove redundant elements immediately improves the greedy solution, particularly when the frequency of elements follows something power-law ish.

You can measure the frequency of each element and weigh uncovered elements by how rare they are (E.g. using entropy). This avoids the primary cause of the above duplicate selections.

You can use lookahead e.g. pick the pair of elements that together improve the score the most but then only commit to one.

You can use rarity weighed random starts, complete using whatever search you have, then retry multiple times.

You can compute new solutions using only the results of prior attempts. etc. etc.

In my experience basically any improvement over the greedy algorithm works on real problems, even before getting to a proper ILP solver. The greedy algorithm is just pathetic and will result in solutions much worse than you get from simple elaborations.

But over and over again you can find people being told to use the greedy algorithm because no polynomial time algorithm is better -- even in instances that are small and where actually enumerating all solutions might be tractable and justified.