セッション１: 組合せ最適化と離散アルゴリズム (Combinatorial Optimization and Discrete Algorithms)

本セッションでは，組合せ最適化と離散アルゴリズム分野において世界的にご活躍されている３名の研究者を迎えて，最新の研究動向をお話を頂く．具体的には，組合せ最適化分野から，グラフ・ネットワーク上の最適化問題として古くから盛んに研究されている「ネットワーク構成問題」と組合せ最適化分野で中心的な役割を果たす「劣モジュラ最小化問題」について解説していただく．また，離散アルゴリズム分野からは，ゲノムやデータマイニングなどにおいて巨大なデータを扱う際に必要な「圧縮データ構造」について解説していただく．

講演

• 定兼 邦彦 （九州大学） 圧縮データ構造とその最新動向
  概要 | プロフィール
• 石井 利昌 （小樽商科大学） 連結度要求を持つネットワーク構成問題
  概要 | プロフィール
• 岩田 覚 （京都大学） 劣モジュラ最適化の最近の進展
  概要 | プロフィール

概要

定兼 邦彦 (Kunihiko Sadakane)
九州大学 (Kyushu University, Department of Computer Science and Communication Engineering)
タイトル： 圧縮データ構造とその最新動向
The Latest Trend of Compressed Data Structures

概要：

大量のデータを扱う場合の問題点として記憶領域の大きさがある． その解決のために近年圧縮データ構造が盛んに研究されている． これは従来のデータ構造のサイズを圧縮し，かつ問合せの計算量 も増えないというものである．これらのデータ構造の基本と，最近の 結果について解説する．

石井 利昌 (Toshimasa Ishii)
小樽商科大学 (Otaru University of Commerce, Department of Information and Management Science)
タイトル：連結度要求を持つネットワーク構成問題
Network Design Problem with Connectivity Requirements

概要：

グラフ理論における連結度の概念は, 種々のネットワークの制御・設計 において，耐故障性に関する基本的な評価尺度として用いられる. 所望の連結度を保証するネットワークを最適構成する問題として， 連結度増大問題と供給点配置問題を取り上げる．近年，これらの問題に対し， 効率的なアルゴリズムの研究が盛んに行われており，また劣モジュラ関数を 用いて一般化された離散最適化問題の研究もされてきている． 本発表では，これらの問題に対する最近の研究結果を紹介する．

岩田 覚 （Satoru Iwata)
京都大学数理解析研究所 (Research Institute for Mathematical Sciences, Kyoto University)
タイトル：劣モジュラ最適化の最近の進展
Recent Progress in Submodular Optimization

概要：

劣モジュラ関数は，行列の階数，ネットワークのカット容量， 多元情報源のエントロピー関数など，応用数学の広範な分野で 現れる集合関数であり，凸関数の離散版として認識されている． 数理計画法においては, 1970年に J. Edmonds によって重要性が 指摘されて以来，効率的に解くことのできる離散最適化問題に 共通の構造として注目されてきた．本講演では，劣モジュラ関数の 最小化を中心に，劣モジュラ最適化の最近の進展を紹介する．