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

Set Cover 問題をひたすら扱う Deterministic LP rounding 要素の最大次数を f とする LP を解き，1/f 以上になっているやつを 1 にする f 近似 Deterministic dual LP rounding 相補性定理 Primal-dual を使うと簡単に Dual 解が求まる Greedy 「コスト/新…

趣旨 アルゴリズム内の処理の一部を指定させる一般的な方法には以下がある． 関数ポインタを使う (qsort 等) 関数オブジェクトを使う (std::sort 等) 仮想関数を使う これらで性能がどう変化するかを測定した． 結果概要 wandbox にて実験した：http://melpo…

探索ノード数を得る IloCplex cplex(model); ... cplex.solve(); cout << "Nodes: " << cplex.getNnodes() << endl; カット数を得る cout << "Cuts: " << cplex.getNcuts(IloCplex::CutClique) << endl; http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/i…

I 田さんが間違えて行ってしまったが起死回生したので有用なメモとしてその時の記録を残す 14:20 成田着 → 爆速でタクシーに乗る 15:20 羽田 国内線第二ターミナルに何故か降ろされる（ANA は国内線ですら第一なので完全に謎） → バスで移動 15:40 羽田 国際…