The best solution might be NP-hard. However we don't need the best, we need one that is good enough, and that is more doable.