Transforming Heuristics

Many of the real problems in the world are NP. Things like Scheduling, Register Allocation, Routing packages, etc. In solving these really hard problems, we invent heuristics. Typically such heuristics are specific to the problem domain. For example, UPS might exploit certain characteristic about the geographical layout of the country; they face a certain subset of all possible graphs, and can exploit those features.

But we know that the NP problems are all reducible to each other. So, don’t the heuristics transform as well?

That is, given a heuristic that works well for the Knapsack problem, how well does that same heuristic (transformed) work on the Travelling Salesman Problem?