読者です 読者をやめる 読者になる 読者になる

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近似です.
  • アルゴリズム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 でまだ使ってない色を探し,その色で塗ろうとする
    • 増大路っぽくスワップしまくるとその色で塗れる