>>31
まず、NP-Hardの定義を勉強しろ。
そして、近似スキームの勉強をしろ。

最適解を求めるという方針ならば、多項式時間はほぼ無理。
（P=NPが証明されたら可能)
分枝切除平面法ならば、最適性の保証つきでかなり速いが、
ランダムなデータを与えると全然だめだ。
なぜなら問題の構造を生かしたカットを入れているから。

近似解法なら多項式時間のがいっぱいあるから調べな。