組合せ数学セミナー
発表内容の概要
多面体の（組合せ的）直径を理解することは，多面体論における基本的な課題であり，
最適化理論にも応用されている．本発表では，整数多面体を取り上げ，その直径の最大
値について議論する．既存研究を概説した後，最近の発表者らの結果＝高次元でタイト
な下界について報告する．本発表の内容の一部は，Antoine Deza氏とLionel Pournin氏
との共同研究に基づく．
Dispersion Problemは施設配置問題の１種であり、施設の候補点集合が与えられ、
そこから任意の２点間の最小距離が最大となるようにk点選ぶ問題である。Dispersion
Problemは２次元ではNP-hardであることが知られている。本発表では１次元における
Dispersion Problemに対して、厳密解を効率的に求めるアルゴリズムと問題設定を
少し変えた新しいモデルについて紹介する。
本発表は中野眞一氏（群馬大学）、赤木俊裕氏（とめ研究所）との共同研究である。
格子暗号は、次世代の耐量子計算機暗号の候補として有力視されている暗号系
である。格子暗号の安全性は、所与の格子基底から最短の非ゼロ格子ベクトル
を探索する問題の困難性を根拠とする。従って、安全かつ実用的な格子暗号を
構成するためには、この問題の計算量を見積ることが重要である。本発表では、
探索における最短格子ベクトルの発見確率が、高次統計量とGram-Charlier展開
により非常に正確に推定できることを示す。
照屋唯紀氏（産業技術総合研究所）、柏原賢二氏（東京大学）との共同研究である。
系統樹は進化の基本的なモデルだが，データにはノイズや不確かさがつきもの
であり，生物同士の類縁関係を一つの木構造で完璧に記述できることはほとん
どない．そのため，系統ネットワークと呼ばれる系統樹を一般化した有向非巡
回グラフを用いてデータを記述し，そこからノイズに相当するアークを除去す
ることで真の系統樹を見つけ出す方法を考えることには，現実的な意義がある．
本講演では，真の系統樹の候補の数え上げ，列挙，最適化，上位ランキングと
いった多種多様な問題を定式化し，それらに統一的な視点でアプローチするこ
とを可能にする系統ネットワークの構造定理を示し，各問題に対する線形時間／
線形時間遅延アルゴリズムを与える．なお，本講演内容の一部（上位ランキン
グ問題のアルゴリズムに関する結果）は牧野和久氏（京都大学数理解析研究所）
との共同研究である．
公平分割問題とは，異なる選好を持つ人々にどのように複数の財を公平に
配分するかを考える資源配分問題のことである. 1948年にHugo Steinhaus
がケーキ分割問題に対する数学的なモデルを提案して以来, 多岐にわたる
学問領域で関心を集めた. 本発表では, グラフの連結制約条件付き公平分
割問題に関する発表者らの成果について紹介する.
本研究では、適応的な意思決定における貪欲法を扱う。貪欲法とは、各ス
テップで最も利得が増えそうな選択肢を選ぶアルゴリズムである。貪欲法
は実装が簡単かつ高速に動作するため、現実のさまざまな場面で用いられ
ているが、その多くにおいて理論的な近似保証は示されていない。本研究
では、「適応的劣モジュラ比」を用いて、適応的な意思決定において貪欲
法に近似保証を与えるための枠組みを提案する。本研究は、坂上晋作氏
（NTTコミュニケーション科学基礎研究所）との共同研究である。
単体的複体を、極大面（＝ファセット）を上端とする区間で分割できるとき、分割可能
という。単体的複体の分割可能性について、基本的な事項や最近の進展状況などを紹介
する。
トップに戻る