高性能近似設(shè)計法関研究

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

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

3、定義,w関係),min(wdnvddv)(重付),(minmax)(HvdwGVvGHw：G頂點v次數(shù)),(Gvd),min(ww定義 ,w関係),min(w),(minmax)(HvdGVvGH：重付w：最大次數(shù)：最大重付次數(shù)w既存近似率l重) 1 (6OlogloglogOl重付32logloglogO：最大次數(shù)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織機構(gòu)造綜絖糸本、綜絖目通。綜絖上昇、上下層分糸間糸通、織物?？棛C裝著綜絖枠多、複雑模様（組織）織物織。3行列問題織方図wfh：糸：糸：綜絖枠織方図行列表現(xiàn)W=PT長目綜絖導(dǎo)入糸、長目綜絖 A、B 通場合長目綜絖動論理和糸上昇決。簡単例普通綜絖使用時長目綜絖導(dǎo)入時綜絖枠枚以上織機製織 （

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

8、 工學(xué)研究科*豊橋技術(shù)科學(xué)大學(xué) 情報工學(xué)系2005年11月參加研究成果(2005年11月） 無線関連 基動的無線網(wǎng)提案 、 証明書分散問題 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)可解性 同期型無線網(wǎng)ARB 衝突検知機能場合、ARB

12、非可解 ARB可解十分條件最適構(gòu)成(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) 山中，伊藤，片山，犬塚，和田：軸方向関共有知識持自律分散群対形狀形成，信學(xué)論（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研究（完全非同期） 協(xié)調(diào)問題 一點集合問題 形狀形成問題協(xié)調(diào)問題可解性理論研究問題定義一點集合問題任意位置配置群決、一點集合問題一點集合： ： 體積持點扱 平面上

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