物理情報システム専攻

Department of Information Processing

理論計算機科学の基礎研究とその応用
伊東 利哉 研究室
専門分野：理論計算機科学、近似アルゴリズム、組合せ応用数学
Home Page：http://www.dac.isl.titech.ac.jp● 研究目的●我々の身の回りに存在する様々な組み合わせ問題（例えば、ネットワーク・符号・情報検索ツールの設計等）に対し、アルゴリズムの観点から理論的検討を行っている。そして、これらの設計と解析を通じて、より効率的なアルゴリズムの実現と離散構造の解明を目指している。

● 研究テーマ●
1．代数的手法および確率的手法による離散構造の解析
1.1

電子文書の類似性判定（最小値独立置換族）

最小値独立置換族は、多数の類似した文書を効率的に特定する際に極めて有用であることが知られている。
しかし、その構成法に関しては、未だ十分に解明されていないのが現状である。そこで、代数的手法を用いて、最小値独立置換族を行列として定式化し、その行列の階数を評価するなどの手法により、（1）最適な最小値独立置換族を構成する際のサイズの下界・上界の導出（2）最適な最小値独立置換族を構成する具体的な手順の開発を理論的側面から検討し、その有効性を探求している（1, 2, 3, 8）。
1.2

k−限定独立置換族の構成

確率的アルゴリズムは、組合せ最適化問題に対して効率的な手法となる場合があるが、その出力は確率的に変動する。そこで、確率的アルゴリズムが出力する解の期待値以上の解を出力する決定性アルゴリズムの設計が重要となる。この際に、小さな標本空間を有する 2−限定独立置換族が有効であることが知られている。
そこで 2−限定独立置換族を任意の整数 k_>2 に対して一般化した k−限定独立置換族に関して考察し、（1）k−限定独立置換族のサイズの下界・上界の導出（2）k−限定独立置換族を構成する具体的な手順の開発を理論的側面から検討し、その有効性を探求している（4）。
1.3

双対符号の距離構造の解析

最小距離 d の線形符号 C に対して、最小距離 d ┴ の双対符号 C ┴ が存在するとき、その符号長の最小値を求める問題は、暗号理論における安全な署名方式の設計に重要な役割を果たすことが知られている。そこで、代数的手法を用いて最小符号長を理論的に導出することにより、最適な双対符号の距離構造を解析している（7）。

2．オンラインアルゴリズム
外国通貨取り引き等に対してアルゴリズムを設計する場合、そのアルゴリズムは、未来の情報を用いず過去の情報のみから現在の動作を決定する必要がある。このようなアルゴリズムを総称して「オンラインアルゴリズム」と呼ぶ。例えば、一カ月後に海外旅行を控えていて、手持ちの 10 万円で出来るだけ多くドルを40入手したいとしよう。もし、この先一カ月で最も円高になる時期が事前に分かっているのなら、そのレートで全額をドルに変えればよいが、これは投資の専門家にとっても難問である。そこで、毎日変動する為替レートを慎重に眺めながら、円を売ってドルを買うタイミングを決めなければならない。では、どのような基準で手持ちの円資金をドルに変えて、出来るだけ多くのドルを手に入れたらよいのだろうか？ これはオンラインアルゴリズムの典型例である。一般的に。オンラインアルゴリズムの効率は競合比により評価される。
そこで、パケット制御における QoS（Quality of Service）に対し、（1）効率的な QoS オンラインアルゴリズムの設計（2）QoS アルゴリズムの効率化の限界の解明を理論的側面から検討し、その有効性を探求している（5, 6）。

3．電子商取引アルゴリズムの理論研究
3.1

最適選好マッチング

複数のユーザが複数の商品に対して、各自の選好度を提示しているとする。ここで、商品供給者は、各ユーザに対して商品を割り当てる際に、ユーザの満足度を最大化することが求められる。このような割り当ては最適選好マッチング（Popular Matching）と呼ばれる。最適選好行マッチングは必ず存在するとは限らないが、ユーザ数に比べて商品数が多い場合に、最適選好マッチングが存在する確率が高くなることが経験的に知られている。そこで、この現象を理論的に解析し、ユーザ数と商品数の比率に関する臨界点が存在することを明らかにしている（9）。
3.2

商品価格設定問題

各ユーザが、購入希望の商品群に対して予算上限を提示しているとする。このとき、商品供給者の目的は、利益が最大となるように各商品の価格を決定することとなる。このような問題は商品価格設定問題と呼ばれる。一般に商品価格設定問題において、利益を最大化する価格を決定することは困難であることが知られているため、効率的な近似アルゴリズムの設計が現実的に重要となる。そこで、様々な価格モデルに対してアルゴリズムを設計し、近似比を理論的に解析することでその有効性を検証している（10）。

● 教員からのメッセージ●
頭の芯を使って、研究を進めよう。そして、アルゴリズムの動作や組合せ離散構造の解析を系統的に捕らえよう。このために、論理思考能力と最後まで考え抜く能力を磨こう。
●参考文献
1. T. Itoh, Y, Takei, and J. Tarui: “On Permutations with Limited Independence，” in Proc. of the 11th ACM-SIAM Annual
Symposium on Discrete Algorithms, pp.37-146 (2000).
2. T. Itoh, Y. Takei, and J. Tarui: “On the Sample Size of k-Restricted Min-Wise Independent Permutations and Other k-WiseDistributions，” in Proc. of the 35th ACM Annual Symposium on Theory of Computing, pp.710-719 (2003).
3. J. Tarui, T. Itoh, and Y. Takei: “A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries，” inProc. of RANDOM-APPROX. Lecture Notes in Computer Science 2764, pp.396-408 (2003).
4. T. Itoh, Y. Takei, and J. Tarui: “Constructing Families of ε-Approximate k-Wise Independent Permutations，” the Transactions ofIEICE, Vol.E87-A, No.5, pp.993-1003 (2004).
5. T. Itoh and T. Nagumo: “Improved Lower Bounds for Competitive Ratio of Multi-Queue Switches in QoS Networks，” theTransactions of IEICE, Vol.E88-A, No.5, pp.1155-1165 (2005).
6. T. Itoh and N. Takahashi: “Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities，” theTransactions of IEICE，Vol.E89-A, No.5, pp.1186-1197 (2006).
7. R. Matsumoto, K. Kurosawa, T. Itoh, T. Kohno, and T. Uematsu: “Primal-Dual Distance Bounds of Linear Codes With
Application to Cryptography，” IEEE Transactions on Information Theory, Vol.52, No.9, pp.4251-4256 (2006).
8. N. Alon, T. Itoh, and T. Nagatani: “On (ε, k)-Min-Wise Independent Permutations，” Random Structures and Algorithms, Vol.31,
No.3, pp.384-389 (2007).
9. T. Itoh and O. Watanabe: “Weighted Popular Matchings，” ArXiv 0710.5338 (2007).
10. R. Hamane, T. Itoh, and K. Tomita: “Approximation Algorithm for the Highway Problem under the Coupon Model,” ArXiv
0712.2629 (2007).

41