Subset-sum can be approximated within 1+epsilon for any requested epsilon>0 [a PTAS]
MAX-3SAT can be approximated within 8/7 and not better. Vertex cover can be aproximated within 2 and its not known if that's optimal.
Set cover can be approximated within O(log n) and not better.
Clique and TSP have no sensible approximation.
I would argue that potentially a loss of factor 2 is not an order of magnitude away from optimal. I don't know what is the situation for markets.
Subset-sum can be approximated within 1+epsilon for any requested epsilon>0 [a PTAS]
MAX-3SAT can be approximated within 8/7 and not better. Vertex cover can be aproximated within 2 and its not known if that's optimal.
Set cover can be approximated within O(log n) and not better.
Clique and TSP have no sensible approximation.
I would argue that potentially a loss of factor 2 is not an order of magnitude away from optimal. I don't know what is the situation for markets.