Well, the problem for the NP-hard algorithm is that the base line is already very efficient. It's like branch prediction. Even the dumbest predictors can be 90% efficient. The perfect solution doesn't have much room to be better. I'd say there are more microsecond level optimization problems left than on the nanosecond or millisecond level.
