3 ms·
For sure: a traveling salesman route under length L, for instance. But what is good enough when combining incompatible people? Less than three vendettas per t
by haroldp 3y ago
For sure: a traveling salesman route under length L, for instance. But what is good enough when combining incompatible people? Less than three vendettas per table? :)
- stncls 3y agoI agree with grandparent that non-optimal solutions are often enough. But just to be complete, since TSP was mentioned here: We could solve TSP instances with >80k cities to optimality back in 2006: https://www.math.uwaterloo.ca/tsp/ https://www.math.uwaterloo.ca/tsp/ The trick is that some types of problems, like TSP or assignment problems, have structure that can be exploited. Of course they remain NP-hard, so as size grows, at some point the computational cost becomes unsustainable. But the point at which this happens is often way further (i.e. for much larger instances) than most imagine.