2 ms·
Logistics is hard in general, is my impression. In fact, most of the interesting problems logistics seem to reduce to NP-complete problems, which has some unfor
by arnsholt 13y ago
Logistics is hard in general, is my impression. In fact, most of the interesting problems logistics seem to reduce to NP-complete problems, which has some unfortunate consequences for finding optimal solutions.
- gizmo686 13y agoThe generalized form of most logistics problems reduce to NP-complete, but we are also almost always working in a system with much more structure than the general problem, so a polynomial time solution may be available. Also, many NP-complete problems can find 'near' optimal solutions in polynomial time. For example, consider the traveling salesman problem in a metric space. We can construct a minimum spanning tree in polynomial time, and we know that traversing this tree takes no more than twice as long as traversing an optimal solution to the traveling salesman problem. By using the triangle inequality, we can further optimize our solution, still in polynomial time.