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 < 0 と仮定する
• アルゴリズム：Greedy に締切が近いやつからやっていく
• 近似値の評価
  • 最適値の lower-bound を得る
  • 近似値の upper-bound を得る

省略：大体おなじ

• 2.2 The k-center problem
• 2.3 Scheduling jobs on identical parallel machines

2.4 The traveling salesman problem

• 今日は symmetric 仮定
• 困難性：一般の場合
  • P≠NP であれば定数近似無理
  • それどころか O(2^n) 近似すら無理
  • ハミルトン閉路問題が帰着できてしまうから
• なので，特別ケースを考えます：metric TSP（三角不等式が成立）
• アルゴリズム1：最小全域木を考えるやつ
  • ２近似です．
• アルゴリズム2：マッチング使うやつ
  • 最小全域木を考え，次数が奇数になっている頂点たちで，minimum weighted matching
  • グラフ H = 最小全域木 T + マッチング M
  • M の重みが 1/2 OPT 以下であることを示せれば良い
    • 最適なもの O から辺を交互に取り出すと，マッチングになっている
    • そのどちらかは，1/2 OPT 以下の最小マッチングである
• 困難性
  • P≠NP であれば 220/219 未満近似は無理 (2006 年)
  • 最近また改善されたって噂

2.5 Maximizing flota in bank accounts

• 問題概要
  • 銀行を k 個選んで float の和を最大化せよ
• 近似アルゴリズム：Greedy
• 証明：submodular

2.7 Edge Coloring

• 問題
  • 最大次数をΔとした時，Δ色は必要
• 困難性
  • Δ=3 の場合，3-edge-colorable か否かは NP-complete
• アルゴリズム：(Δ+1)-approximation（すごい）
  • 辺を順に塗っていく．辺 (u, v_0) を塗ろうとしているとする．
  • v_0 でまだ使ってない色を探し，その色で塗ろうとする
  • 増大路っぽくスワップしまくるとその色で塗れる