C08 高性能近似アルゴリズムの設計法に関する研究 平田富夫(名古屋大学) 藤戸敏弘(豊橋技術科学大学) 和田幸一(名古屋工業大学) 小野孝男(名古屋大学) 目次 1.グラフと集合問題の研究成果(藤戸敏弘) 2.グラフ問題の研究成果(平田富夫) 2-1 重み付き独立集合問題 2-2 均等辺彩色問題のアルゴリズム 2-3 ブール行列のランク問題の応用 3.分散関係の研究成果(和田幸一) 研究成果(藤戸敏弘) • グラフ問題 – 頂点被覆の一般化(被覆容量/要求量付き部分被覆)に 対する2倍近似アルゴリズム – 連結頂点被覆および木状被覆に対する2倍近似NCアル ゴリズム – 最小コスト木状被覆に対する2倍近似アルゴリズム • 集合問題・その他 – 被覆型0-1整数計画に対する組合せ的近似アルゴリズム – 最小コスト集合充填(コスト制約有)に対する局所改善法 の改良 – 最小コスト3-集合被覆(コスト制約有)に対する貪欲法の 改良 – k-集合多重被覆に対する貪欲法の改良 – 劣モジュラ整数被覆に対する近似アルゴリズム 2-1.重み付き独立集合問題 • 独立集合問題(Independent Set problem) 入力:グラフG=(V,E)、 頂点の重み w: V→R 出力:独立集合 V’ ⊆ V で、含まれる頂点の重みの総和が最小のもの 既知結果: (重みなし) 現状と目標: d 1 2 d w 1 2 2d 3 5 ? d log log d O log d d w log log d w O log d w WG2005 (Y. Kako, T. Ono, T. Hirata, M. Halldorsson) 重み付き次数 ●重み付き次数d w (v, G) の定義 d w (v, G ) w( N G (v)) wv (以後必要の無いときはGの引数は省略) wv:頂点vの重み w(X):頂点集合Xに含まれる頂点の重みの総和 NG(v):頂点vに隣接する頂点集合 重み付き平均次数 :最大次数 w:最大重み付き次数 ●定義 d d (v ) dw v n w d (v) w( N (v)) w d v v W v W ●Δ,Δwとの関係 d w min( , w ) d min( , w ) v v W w (v ) d :平均次数 d w:重み付き平均次数 d (v) :頂点vの次数 重み付きインダクティブネス ●定義 max min d (v, H ) H G vV ( G ) w max min d w (v, H ) H G vV ( G ) ● Δ,Δwとの関係 :最大次数 w:最大重み付き次数 :インダクティブネス w :重み付きインダクティブネス w min( , w ) min( , w ) d (v, G ):グラフGにおける頂点vの次数 既存の近似率 重みなし 重み付き 6 O (1) Halldórsson and Radhakrishnan [1994] log log O log Vishwanathan [1996] 2 3 Halldórsson and Lau [1997] log log O log Halldórsson [2000] Δ:最大次数 既存の近似率 重み付き 1 2 Hochbaum [1983] log log O log Halldórsson [2000] :インダクティブネス w 1 2 (Greedy+LP) w log log w O log w (Greedy+SDP) w :重み付きインダクティブネス 2-2.均等辺彩色問題 (Nearly Equitable Edge Coloring) • Input: multigraph G=(V,E) and color set C={1,2,…,k} • Output: edge coloring π such that for any vertex v∈V and colors i, j∈C d (v, i) d (v, j ) 2 d (v, i) : number of edges incident to v and colored with i nearly equitable edge coloring using 3 colors Previous Results and New Results Previous New running time Hilton & de Werra ’82 O(km ) Nakano et al. ’95 O m / k mn algorithm running time BALCOL O m2 / k RANCOL O m3 / 2 n1/ 2 / k 1/ 2 2 2 m E ,n V ,k C RECCOL Omn log m /kn 1 BALCOL: Balanced Coloring RANCOL: Random Coloring RECCOL: Recursive Coloring X. Xie, M. Yagiura, T. Ono, T. Hirata, U. Zwick Comparison of Results algorithm HdW’82 O km2 NSN’95 O m / k mn BALCOL O m2 / k RANCOL RECCOL k O(1), m n running time 2 Om 3 / 2 1/ 2 n O n 2 /k 1/ 2 Omn log m /kn 1 O n (3 1) / 2 O n 1 log n 2-3.ブール行列のランク問題 織機の構造 綜絖 ・たて糸は1本ずつ、綜絖の目に通されている。 ・綜絖の上昇により、上下2層に分けられたたて糸の間によこ糸が通され、織物となる。 ・織機に装着された綜絖枠が多いほど、複雑な模様(組織)の織物を織ることができる。 織方図 w :たて糸 f :よこ糸 h :綜絖枠 織方図の行列表現 W=PT 長目綜絖の導入 たて糸が、2つの長目綜絖 A、B に通っている場合 長目綜絖の動きの論理和でたて糸が上昇するかどうかが決まる。 簡単な例 普通綜絖のみ使用時 長目綜絖導入時 { 3 { 4 { { 4 3 綜絖枠4枚以上の織機で 綜絖枠3枚の織機で 製織できる (すべてのたて糸は 製織できる(真ん中の2本のたて糸は 1つの綜絖の目を通る) 2つの長目綜絖の目を通る) ブール行列Wの階数 r W P T r :長目綜絖を導入したときに必要な綜絖枠枚数 ブール階数 r を求める問題はNP困難。 実験結果の例(1) 提案アルゴリズムにより、必要な綜絖枠枚数が減った組織の例 グレーシアン織り 織物の外観 織方図 普通綜絖のみ使用時 提案アルゴリズム 綜絖枠24枚 綜絖枠15枚 実験結果の例(2) 三重織り 織物の外観 織方図 普通綜絖のみ使用時 提案アルゴリズム 綜絖枠20枚 綜絖枠12枚 C08班:活動のまとめ(平田、藤戸) • グラフ問題及び集合問題の近似アルゴリズムを与 えた. • 重み付き次数を提案し、独立集合問題の近似アル ゴリズムを解析した. • 均等辺彩色問題のランダムアルゴリズム、再帰アル ゴリズムを与えた. • ブール行列のランク問題の発見的解法を織機の問 題に応用した. C08: 高性能近似アルゴリズムの設計法に関する 研究成果報告(分散班) 平田 富夫* †和田 幸一** 藤戸 敏弘*** 小野 孝男* *名古屋大学 大学院 情報科学研究科 **名古屋工業大学 大学院 工学研究科 ***豊橋技術科学大学 情報工学系 † 2005年11月から参加 研究成果(2005年11月~) • 無線ネットワーク関連 – クラスタに基づいた動的無線網の提案 – ブロードキャスト、ゴシップなど • 証明書分散問題 – 2-近似アルゴリズム • 自律分散ロボット – エラーコンパスを持つロボットの1点集合問題 無線ネットワーク関連 • (1) J.Uchida, I.A.K.M.Muzaidal, Y.Katayama, W.Chen, K.Wada, Construction and maintenamce of a cluster-based architecture for sensor networks, 39th Hawaii International Conference on System Science(HICSS-39),1-10 (2006-1) • (2) W. Chen, A.K.M.M. Islam, M. Malkani, A. Shirkhodaie, K. Wada, M. Zein-Sabatto, Novel broadcast/multicast protocols for dynamic sensor networks, 9th Workshop on Advances in Parallel and Distributed Computational Models(in 21st IEEE International Parallel and Distributed Processing Symposium)(2007-03). • (3) J. Uchida, W. Chen, K. Wada, Acknowledged Broadcasting and Gossiping in ad hoc radio networks, Theoretical Computer Science, Vol. 37, 1-3, pp.43-54 (2007-05). • N. Inaba, K. Wada, Efficient Initialization Algorithms on Single-hop Radio Networks, to appear in IEICE Transactions on Information and Systems. • W. Chen, A.K.M.M. Islam, Y. Katayama, J. Uchida, K. Wada, Construction and maintenance of a novel cluster-based architecture for ad hoc sensor networks, to appear in the Journal of Ad Hoc and Sensor Wireless Networks. ARB (Acknowledged Radio Broadcast)の可解性 • 同期型マルチホップ無線網におけるARB – 衝突検知機能がない場合、ARBは非可解 – →ARBが可解となるための十分条件と最適なア ルゴリズムを構成(2007-05 TCS) 証明書分散問題 (1) H.Zheng, S.Omura, J.Uchida, K.Wada: An optimal certificate dispersal algorithm for mobile ad hoc networks, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E88-A, 5, 1267-1273, 2005-5 (2) H.Zheng, S.Omura, K.Wada An approximation algorithm for minimum certificate dispersal problems, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A,551-558, 2006-2 自律分散ロボット (1) 山中,伊藤,片山,犬塚,和田: 軸の方向に関する共有知識を持たない自律分散ロボット群に対する形状形 成アルゴリズム,信学論(DーI), J88-D-I, 4, 739-750,2005-4 (2) Y. Katayama, Y. Tomida, H. Imazu, N. Inuzuka, K. Wada Dynamic Compass Models and Gathering Algorithms for Autonomous Mobile Robots, to appear in 14th Colloquium on Structural Information and Communication Complexity(Sirocco 2007) ロボットの共有知識と問題の可解性 背景 • 自律分散ロボット群の理論モデル – 能力の弱いロボットモデル • 鈴木・山下らの研究 • G.Prencipeらの研究(完全非同期モデル) 協調問題の可解性についての理論研究 • 協調問題 – 一点集合問題 – 形状形成問題 問題定義 一点集合問題 任意の位置に配置されたロボット群を あらかじめ決められていない、ある一点 に集合させる問題 一点に集合 :ロボット ロボットモデル • • • • ロボットは体積を持たない点として扱う 平面上を自由に移動できる 外見で区別できない(個別のIDも持たない) 通信能力を持っていない ロボットモデル • 待機、観測、計算、移動の状態を繰り返して動作 – – – – 待機:何もしない 観測:ロボット群の配置を観測 計算:観測結果を用いて、目的地を計算 移動:計算された目的地に移動 サイクル (途中で止まることもありうる) 1サイクル • 以前のサイクルにおける情報を記憶できない 時刻 待機 観測 計算 移動 • ロボット群は完全に非同期で動作する • ロボットの視界に制限は無い ロボットモデル • 全てのロボットは同じアルゴリズムを実行する • ロボットは独自の直交座標系を持つ – 原点、単位距離、x,y軸の傾き、系(右手/左手) いつも自分のいる場所を原点とする すべて右手系 • ロボットは、一つのコンパスを持つ – 北の方角を指し示すデバイス – コンパス示す北と座標系のy軸の方向が一致 一点集合問題の既存の結果 • 座標系のx,y軸が一致 • 座標系のx,y軸が不一致 一点集合できる 一点集合できる 一点集合できない 一点集合できない • 2台のロボットの場合 – ロボット間でコンパスのズレが45゜以下 コンパスのモデルが • 今津(’05) 統一されていない。 •コンパスが一致 X.Defagoら(’06) コンパスが不一致 本研究の目的、結果 • コンパスのモデルを提案 – ズレのあるコンパス → 故障したコンパス • 既存の結果を上回るアルゴリズムを提案 – さらに大きな角度のズレをゆるす – 時刻によって方向が変化してもよい 故障したコンパスのモデルの定義 • 動的なコンパス 弱 強 – Full Dynamic Compass FDC:任意の時刻で向きが変化する – Semi Dynamic Compass SDC:任意のサイクルで向きが変化する – Fixed Compass FXC:すべてのサイクルで変化しない • 不一致なコンパス 弱 強 – α-相対不一致:任意の2台間にαのズレ – α/2-絶対不一致:絶対座標に対してα/2のズレ α α/2 絶対北 α/2 故障したコンパスのモデル 不一致なコンパス 強 モデルの強さ α/2-絶対不一致 弱 α-相対不一致 弱 動 的 な コ ン パ ス FDC モ デ ル の 強 さ 強 SDC FXC 既存の結 果 2台、α≦45゜:一点集合可能 今回提案するアルゴリズム 不一致なコンパス 強 モデルの強さ α/2-絶対不一致 弱 動 的 な コ ン パ ス FDC モ デ ル の 強 さ 強 SDC FXC 弱 α-相対不一致 2台以上 :一点集合不可能 絶対:α>0゜ / 相対:α≧0゜ 今津のアルゴリズム が そのまま使える 2台、α≦45゜: 2台、α≦45゜:一点集合可能 2台、α≦60゜:一点集合可能 一点集合可能 結果 不一致なコンパス 強 モデルの強さ α/2-絶対不一致 弱 動 的 な コ ン パ ス FDC モ デ ル の 強 さ 強 SDC FXC 弱 α-相対不一致 2台以上 :一点集合不可能 絶対:α>0゜ / 相対:α≧0゜ 2台、α≦45゜: 一点集合可能 2台、α≦60゜:一点集合可能 まとめ • • • • 故障したコンパスのモデルを提案 60゜-相対不一致FXCの一点集合アルゴリズム FDCを持つロボット一点集合不可能性 45゜/2-絶対不一致SDCの一点集合アルゴリズム 今後の課題 • α-相対不一致SDCの一点集合問題の可解性 • 角度αの限界 • ロボット3台以上のアルゴリズム
© Copyright 2025 ExpyDoc