The computational complexity is a bit of a red herring. Finding the most optimal solution is hard. But if you settle for a close-to-optimal solution, then it can be solved in a much more reasonable time.