福永 拓郎 （京都大学） Magnús M. Halldórsson (Reykjavik University) 永持 仁 （京都大学） Robust Cost Colorings 福永 拓郎 （京都大学） Magnús M. Halldórsson (Reykjavik University) 永持 仁 （京都大学） 特定領域研究「新世代の計算限界　−その解明と打破−」 平成１９年度 第２回 全体会議 ２００７年１２月１５日　東北大学

グラフの節点彩色 V の独立集合分割 ｛C1, …, Ck } つまり，V = C1 ∪ …∪Ck Ci ∩ Cj =  (i ≠ j ) E [Ci ] = 

応用例：機械スケジューリング 時刻

応用例：機械スケジューリング 時刻 　　　色の数 = 機械の数 → 最小化

今日の話 コスト関数付き彩色問題 に対する ロバストなアルゴリズム コスト関数：色数最小化以外にもたくさんの目的関数がある Threshold Coloring [Bodlaendar, Jansen,95] Probabilistic Coloring [Murat, Paschos, 06] Entropy Coloring [Cardinal, Fiorini, Joret, 05] 　… ロバスト：　どんな目的関数に対しても，そこそこいい解をくれる 前もって目的関数が分らなくてもいい（オンライン問題） 途中で目的関数が変わってもいい

コスト関数付き彩色問題 問題 入力: 無向グラフ G = (V, E), コスト関数 g: 2V → Q 制約：　　 {C1, C2 ,…, Ck }： Vの彩色 目的関数： g(C1) + g(C2) + …+ g(Ck) →最小化 コスト関数 g: 重み依存 ある　w: V → Q, f : Q → Q　に対して g(C) = f ( w(C) ) ただし， w(C) = vC w(v)

応用例：機械スケジューリング 機械1台の値段 w: 仕事を外注した時の料金 f (w(C)) := min{w(C), 7 } 4 2 6 5 3 2 5 9 6

応用例：機械スケジューリング 機械1台の値段 w: 仕事を外注した時の料金 f (w(C)) := min{w(C), 7 } 4 5 2 コスト= 7 2 2 コスト= 4 5 6 コスト= 7 3 1 コスト= 4 2 6 9 コスト= 7 合計：29 = 3台の機械を買って，残りの仕事は外注したときの値段

彩色問題の色々なコスト関数 色数最小化 Rent or Buy 多段階 e/(e-1)‐近似 重み依存 エントロピー g(C) = f (w(C)):=1 g(C) = f (w(C)) = min { w(C), T } f f f T w(C) w(C) w(C) e/(e-1)‐近似 重み依存 エントロピー g(C) = f (w(C)) = －w(C) ln(w(C)) 確率的 g(C):= 1－vC (1-w(v)) 重み非依存 f Lpノルム g(C):= (vC w(v)p )1/p w(C) 1

結果 ｆ ：単調非減少・凹 ｆ ：単調非減少 G:インターバルなど ４‐近似 ８‐近似 G:パーフェクト w(v) = 1, v V f : 単調非減少・凸は |V |色で塗るのがコスト最小 ｆ ：単調非減少・凹 ｆ ：単調非減少 G:インターバルなど ４‐近似 ８‐近似 G:パーフェクト w(v) = 1, v V ６‐近似 １２‐近似

彩色問題の色々なコスト関数 色数最小化 Rent or Buy 多段階 e/(e-1)‐近似 重み依存 エントロピー g(C) = f (w(C)):=1 g(C) = f (w(C)) = min { w(C), T } f f f T w(C) w(C) w(C) e/(e-1)‐近似 重み依存 エントロピー g(C) = f (w(C)) = －w(C) ln(w(C)) 確率的 g(C):= 1－vC (1-w(v)) 重み非依存 f Lpノルム g(C):= (vC w(v)p )1/p w(C) 1

集合関数によるアプローチ g : polymatroid U  W, v  W ⇒ g(U + v) + g(W)  g(U) + g(W +v) U  W ⇒ g(U)  g(W) 0  g(U)  |U | 定理 [Gijswijt, Jost, Queyranne, 06] G: 補インターバルグラフ，コスト関数 g: polymatroid のとき，コスト最小化彩色問題はNP-困難．

集合関数によるアプローチ g: value-polymatroid g(U)  g(W), v  U ⋃ W ⇒ g(U + v) + g(W)  g(U) + g(W +v) U  W ⇒ g(U)  g(W) 0  g(U)  |U| 定理 [Gijswijt, Jost, Queyranne, 06] G: 補インターバルグラフ，コスト関数 g: value-polymatroid のとき，コスト最小化彩色問題は多項式時間計算可能．

k 色部分グラフ問題のアルゴリズムを繰り返し適用 f : 単調凹関数のとき k 色部分グラフ問題のアルゴリズムを繰り返し適用 ポイント：

k色部分グラフ問題 問題 入力: グラフ G = (V, E), 重み w: V → Q 制約： G[U] が k-彩色可能 目的関数：　w(U) → 最大化 次のグラフクラスに対して，多項式時間アルゴリズム インターバルグラフ [Yannakakis, Gavril, 87] 置換グラフ [Saha, Pal, 03] 比較可能グラフ [Cameron, 85] 補比較可能グラフ [Frank, 80]

アルゴリズム：凹関数 L := lg χ(G) for i := 0 to L－1 A1 最大重み2i色部分グラフ A0 AL L := lg χ(G) for　i := 0 to L－1 最大重み2i色部分グラフ Ai  V を求め，2i色で塗る G := G － Ai end for 残った節点をALとし，χ(G)色で塗る A1 A0 A2 AL-1 ・・・

アルゴリズム解と最適解の比較 アルゴリズムの解： 最適解： 2i色  χ(G)色 ・・・ ・・・ A0 A1 A2 Ai AL-1 AL B0 B1 B2 Bi BL*-1 BL* 2i-1色 ・・・ 最適解： L* = log χOPT L*  L B3

w(A0)+w(A1)+ ・・・ +w(Ai)  w(B0)+w(B1)+ ・・・ +w(Bi) for i アルゴリズム解と最適解の比較 A0 ⋃ A1 ⋃ ・・・ 　　　⋃ Ai-1 1+20+21+・・・+2i-1 = 2i色 B0 ⋃ B1 ⋃ ・・・ ⋃ Bi  w(Ai) w(A0)+w(A1)+ ・・・ +w(Ai)  w(B0)+w(B1)+ ・・・ +w(Bi) for i

近似比  i=0 2i f ( w(Ai) / 2i )  i=0 2i f ( w(Bi) / 2i ) w(A0)+w(A1)+ ・・・ +w(Ai)  w(B0)+w(B1)+ ・・・ +w(Bi) for i w(Ai)+w(Ai+1)+ ・・・ +w(AL*)  w(Bi)+w(Bi+1)+ ・・・ +w(BL*) for i アルゴリズムのコスト 凹性より  i=0 2i f ( w(Ai) / 2i ) L* 単調・凹性と 上の関係より  i=0 2i f ( w(Bi) / 2i ) L*

最適解のコスト     4 Bi Bi+1  f (w(B0)) + i=1 2i-1 f ( w(Bi+1) / 2i ) の重み  の重み w(Bi+1)/2i … … 2i-1 2i 最適解のコスト  f (w(B0)) + i=1 2i-1 f ( w(Bi+1) / 2i ) L*-1 よって， 最適解のコスト アルゴリズムのコスト f (w(B0)) + i=2 2i-2 f ( w(Bi) / 2i-1) L* i=0 2i f ( w(Bi) / 2i )   4

k 色部分グラフ問題の(α, β)-近似 問題 最大化： w(U) 制約： G[U] が k-彩色可能 U  V が次の条件を満たすとき， (α, β)-近似解であるという． (ただし， α, β  1). G[U] が αk色で彩色可能 最適解 U* に対して，w(U*)  βw(U) 最適解 U* に対して，βw(V－U*)  w(V－U) 定理 G: パーフェクトグラフのとき，t に対し α = t, β = t /(t -1). 特に，t = 1.5 とすれば，α = 1.5, β = 3.

近似比 ( ) ×β  i=0 2i f( w(Ai) / 2i ) i=0  2i f ( w(Ai) /  2i ) w(A0)+w(A1)+ ・・・ +w(Ai)  w(B0)+w(B1)+ ・・・ +w(Bi) for i w(Ai)+w(Ai+1)+ ・・・ +w(AL*)  w(Bi)+w(Bi+1)+ ・・・ +w(BL*) for i ×β ( )  i=0 2i f( w(Ai) / 2i ) L* アルゴリズムのコスト 凹性より i=0  2i f ( w(Ai) /  2i ) L*  i=0 2i f( w(Bi) / 2i ) L* 単調・凹性と 上の関係より i=0  2i f(  w(Bi) /  2i ) L*

近似比 =   4 i=0 3・2i-1 f ( w(Bi) / 2i-1 ) i=0 2i f ( w(Bi) / 2i ) L* i=0 2i f ( w(Bi) / 2i ) L* i=0 2i f( w(Bi) / 2i ) L* アルゴリズムのコスト 6   4 f(w(B0)) + i=2 2i-2 f( w(Bi) / 2i-1 ) L* 最適解のコスト

⇒ アルゴリズムが計算する解は任意のコスト関数の最適解を同時に近似 !!! ロバスト性（単調凹コスト関数） アルゴリズムはf を見ずに解を計算している!! ⇒　アルゴリズムが計算する解は任意のコスト関数の最適解を同時に近似 !!! 定理： k色部分グラフ問題が解けるグラフクラスに対しては，ロバストな4-近似解，パーフェクトグラフに対しては，ロバストな6-近似解が多項式時間計算可能． 定理： グラフクラスに関わらず，ロバストな4-近似解となる彩色が存在する．

f : 単調関数，w(v)=1 (vV) のとき ポイント：

単調コスト関数 f → f*   Cの C*の |C|=x f(x) f *(x):=min1yx f(y)・x/y コスト x C*x/y ・・・ |C*i |  y f(x) f *(x):=min1yx f(y)・x/y  　  コスト Cの C*の x

f* →f**   2×Cの Cの f **:=最小凹関数 s.t. f **  f* f *(x):=min1yx f(y)・x/y f **:=最小凹関数 s.t. f **  f*   コスト 2×Cの Cの x

2近似   Cの C*の   2×Cの Cの C の      コスト コスト 2×OPTの コスト 2×OPTの  　  コスト Cの C*の  　  コスト 2×Cの Cの C の  2×OPTの コスト  2×OPTの コスト  ×OPTの  コスト ALGの  コスト ALGの  ALG*の コスト 定理 f : 単調関数，w(v)=1 (v  V) のとき， 多項式時間で 2-近似可能．ただし， は単調凹関数に対する近似比．

ロバスト性（単調コスト関数） アルゴリズム 凹関数 f ** に対する-近似解を求める． 近似解の各色 C に対し，y*:= arg min1 y  |C| f(y) ・ |C| / y　 を計算し，Cをサイズy*以下の色に分割する． 　　 ⇐ 関数は見ない ⇐ f を見る 定理 分割によって，任意の単調コスト関数，w(v)=1 (v  V)に 対する8-近似解が得られるような彩色が存在する．

まとめ 彩色問題と色々なコスト関数 k色部分グラフ問題と(α, β)-近似 単調凹コスト関数，重みつきの場合とロバスト性 単調コスト関数，重み一定の場合とロバスト性