Oh sure, I wasn't intending to comment on the NP-hardness but only on the accuracy of the approximation in practice.

There is a lovely paper disproving the all-public-information efficient market hypothesis, assuming computationally bound actors by showing how to embed market inefficiency into a set of trades that can only be removed by solving a NP-hard problem. :)