[mzl]

The paper claims NP-completeness AFAICS, so I thought that was what you meant. Sorry if I misunderstood.

There are problems that have approximations that can get arbitrarily close to the optimum. One particularly interesting case IMHO are so-called polynomial approximation schemes. These schemes can be used to create an approximation algorithm for any choice of approximation factor and that algorithm will have a polynomial time complexity, but the polynomial will depend on the actual approximation factor chosen.

I agree that it is an interesting problem to study, especially since it meshes well with my own biases that the efficient market hypothesis is too strong.