講義メモ

[講義メモ]Computational Intractability(4/28)

前回までとは少し話が変わって,Integer and linear programの話に.

– 簡単なはなしでは…
Data a1, a2, … anと定数b, c1,c2,…,cnがあるときにz=\sum c_i x_i
\sum a_i x_i \leq bの条件下で最大化する.ただしxiは0以上の変数

– 例として… Kanpsack Problem, Sushi problem, 2-machine scheduleなど.

– 例 subset-sub problem
3-SAT \leq_p SUBSET-SUMなどをやる.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です