平成23年3月 先端暗号フロンティアセミナー アブストラクト


  


        • 宮野 英次 (九州工業大学)
  

  

    題名: 資源増加を許したOVSF符号割当問題に対するオンラインアルゴリズム


  

  

    アブストラクト: 直交可変拡散率（OVSF）符号の割当てをオンライン問題として定式化した問題，特に，ErlebachらによりSTACS'04で導入された資源増加を許すモデルについて考える．本講演では，OVSF 符号木の高さ h に対して 2 \lg^{*} h 個の符号木を利用する 2-競合アルゴリズムを紹介する．このアルゴリズムでは，Chan らによってCOCOON'09で提案された 3h/8 + 2 個の符号木を利用する 2-競合アルゴリズムと比較して，符号木の数を大きく減らすことができている．これは朝廣雄一氏(九州産業大学)，上米良謙太氏(九州工業大学)との共同研究である．

The 2nd Meeting for Cryptology Frontier Group Abstract




  


     • Eiji Miyano (Kyushu Institute of Technology)
  

  

    Title: Online Algorithms for OVSF Code Assignment with Resource Augmentation

  

  

    Abstract: In this talk, we study the online OVSF (Orthogonal Variable SpreadingFactor) code assignment problem with resource augmentation introduced by Erlebach et al. in STACS'04. We propose a 2-competitive algorithm with help of 2 \lg^{*} h trees for the height h of the OVSF code tree, which substantially improves the previous resource of 3h/8 + 2 trees shown by Chan et al. in COCOON'09. This is joint work with Yuichi Asahiro (Kyushu Sangyo University) and Kenta Kanmera (Kyushu Institute of Technology).
[戻る ]