高性能近似设计法関研究

1、高性能近似設計法関研究平田富夫（名古屋大学）藤戸敏弘（豊橋技術科学大学）和田幸一（名古屋工業大学）小野孝男（名古屋大学）目次集合問題研究成果（藤戸敏弘）問題研究成果（平田富夫）重付独立集合問題均等辺彩色問題行列問題応用分散関係研究成果（和田幸一）研究成果（藤戸敏弘） 問題 頂点被覆一般化（被覆容量要求量付部分被覆）対2倍近似 連結頂点被覆木状被覆対2倍近似NC 最小木状被覆対2倍近似 集合問題他 被覆型0-1整数計画対組合的近似 最小集合充填（制約有）対局所改善法改良 最小3-集合被覆（制約有）対貪欲法改良 k-集合多重被覆対貪欲法改良 劣整数被覆対近似重付独立集合問題独立集合問題（）入力：（

2、，）、頂点重 w: 出力：独立集合、含頂点重総和最小既知結果：既知結果：（重）（重）現状目標：？現状目標：？21ddddOlogloglogwwwdddOlogloglog21wd532 d（Y. Kako, T. Ono, T. Hirata, M. Halldorsson）重付次数vGwwvNwGvd)(),(重付次数定義wv:頂点v重NG(v):頂点v隣接頂点集合w(X):頂点集合X含頂点重総和),(Gvdw（以後必要無G引数省略）重付平均次数：最大次数：最大重付次数：平均次数：重付平均次数wdwdWvdwWvNwWvdwdvwvvvvw)()()(：頂点v次数)(vd),min(wwd

3、定義,w関係),min(wdnvddv)(重付),(minmax)(HvdwGVvGHw：G頂点v次数),(Gvd),min(ww定義 ,w関係),min(w),(minmax)(HvdGVvGH：重付w：最大次数：最大重付次数w既存近似率l重) 1 (6OlogloglogOl重付32logloglogO：最大次数Halldrsson and Radhakrishnan 1994uuVishwanathan 1996Halldrsson 2000Halldrsson and Lau 1997既存近似率l重付logloglogO：Hochbaum 1983u21uHalldrsson 2000

4、：重付uu21wwwwwOlogloglog(Greedy+LP)(Greedy+SDP) Input: multigraph G=(V,E) and color set C=1,2,k Output: edge coloring such that for any vertex vV and colors i, jCnearly equitable edge coloring using 3 colors number of edges incident to v and colored with i: ),(ivd2),(),(jvdivd均等辺彩色問題(Nearly Equitable

5、Edge Coloring)Previous Results and ResultsPreviousNewrunning timeHilton & de Werra 82Nakano et al. 95algorithmrunning timeBALCOLRANCOLRECCOLkmO/21/logknmmnO2/12/12/3/knmO)(2kmOmnkmO/2CkVnEm,BALCOL: Balanced Coloring RANCOL: Random ColoringRECCOL: Recursive ColoringX. Xie, M. Yagiura, T. Ono, T.

6、Hirata, U. Zwickalgorithmrunning timeHdW82NSN95BALCOLRANCOLRECCOLComparison of ResultsmnkmO/22kmO1/logknmmnOkmO/22/12/12/3/ knmOnmOk),1 (2nOnnOlog12/ )13(nO織機構造綜絖糸本、綜絖目通。綜絖上昇、上下層分糸間糸通、織物。織機装着綜絖枠多、複雑模様（組織）織物織。3行列問題織方図wfh：糸：糸：綜絖枠織方図行列表現W=PT長目綜絖導入糸、長目綜絖 A、B 通場合長目綜絖動論理和糸上昇決。簡単例普通綜絖使用時長目綜絖導入時綜絖枠枚以上織機製織 （

7、糸綜絖目通）綜絖枠枚織機製織（真中本糸長目綜絖目通）4343行列W階数 r ：長目綜絖導入必要綜絖枠枚数階数 r 求問題NP困難。WPT実験結果例（）織普通綜絖使用時綜絖枠24枚提案綜絖枠15枚織物外観織方図提案、必要綜絖枠枚数減組織例実験結果例（）三重織普通綜絖使用時綜絖枠枚提案綜絖枠12枚織物外観織方図 問題及集合問題近似与 重付次数提案、独立集合問題近似解析 均等辺彩色問題、再帰与 行列問題発見的解法織機問題応用班：活動（平田、藤戸）C08: 高性能近似設計法関研究成果報告(分散班）平田 富夫*和田 幸一*藤戸 敏弘*小野 孝男*名古屋大学 大学院 情報科学研究科*名古屋工業大学 大学院

8、 工学研究科*豊橋技術科学大学 情報工学系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-

9、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 Sym

10、posium)(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 I

11、nformation 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

12、非可解 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.WadaAn approxi

13、mation algorithm for minimum certificate dispersal problems, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A,551-558, 2006-2自律分散(1) 山中，伊藤，片山，犬塚，和田：軸方向関共有知識持自律分散群対形状形成，信学論（DI）, J88-D-I, 4, 739-750,2005-4(2) Y. Katayama, Y. Tomida, H. Imazu, N. Inuzuka, K

14、. WadaDynamic Compass Models and Gathering Algorithms for Autonomous Mobile Robots,to appear in 14th Colloquium on Structural Information and Communication Complexity(Sirocco 2007)共有知識問題可解性背景 自律分散群 能力弱 鈴木山下研究 G.Prencipe研究（完全非同期） 協調問題 一点集合問題 形状形成問題協調問題可解性理論研究問題定義一点集合問題任意位置配置群決、一点集合問題一点集合： ： 体積持点扱 平面上

15、自由移動 外見区別（個別ID持） 通信能力持 待機、観測、計算、移動状態繰返動作 待機：何 観測：群配置観測 計算：観測結果用、目的地計算 移動：計算目的地移動（途中止） 以前情報記憶 群完全非同期動作 視界制限無時刻待機観測計算移動1 全同実行 独自直交座標系持 原点、単位距離、x,y軸傾、系（右手/左手） 、一持 北方角指示 示北座標系y軸方向一致自分場所原点右手系一点集合問題既存結果 座標系x,y軸一致 座標系x,y軸不一致 2台場合 間45以下 今津（05） X.Defago（06）一点集合一点集合一点集合一点集合一致不一致統一。本研究目的、結果 提案 故障 既存結果上回提案 大角度 時刻方向変化 FDC:任意時刻向変化 SDC：任意向変化 FXC：変化 -相対不一致：任意2台間 /2-絶対不一致：絶対座標対/2 Full Dynamic Compass Semi Dynamic Compass Fixed Compass故障定義/2/2絶対北強弱強弱故障FDCSDCFXC/2-絶対不一致-相対不一致不一致動的強強強強弱弱2台、45：一点集合可能既存結果2台、45：一点集合可能今回提案F