3 ms·
Generally with NP-complete problems - that small constant factor is still often an order of magnitude away from optimal (path finding/search/salesman/shortest s
by confluence 14y ago
Generally with NP-complete problems - that small constant factor is still often an order of magnitude away from optimal (path finding/search/salesman/shortest subsequence etc).
- sold 14y agoIn general, approximation of NP-complete problems is not that simple. Assuming P /= NP, 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.