[mzl]

The concept of NP-complete is different form the concept of np-hard to approximate in any way. The question if a particular problem is hard to approximate is typically a diverse and interesting research area, that does not have obvious answers.

For example, it has been proven that the well-known traveling salesperson problem on metric instances (i.e., instances satisfying the triangle inequality) can not be approximated within around 1.008 unless P=NP, and there is an approximation algorithm that has factor 1.5.

I have not read the above pre-print, but from a cursory glance it does not discuss theoretical approximation hardness at all. It does have a section on approximations, but it is hand-wavy and fluffy and uses a colloquial/non-strict meaning for approximation.

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