2014-04-30から1日間の記事一覧

Greedy Algorithms and Local Search (Chapter 2, The Design of Approximation Algorithms)

2.1 Scheduling jobs with deadlines on a single machine 問題:スケジューリング.max(締切を過ぎた時間) を最小化したい NP-hard (0 以下か否かの判定だけでも strongly NP-hard) 以下,d_i アルゴリズム:Greedy に締切が近いやつからやっていく 近似値…