[SolarNet]

This is why I support the authors research, without knowing if it even is NP complete (as this paper claims) we are faced with it being NP hard. Without studying the problem, we can't even begin to find approximation algorithms.

[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.