組合せ数学セミナー
発表内容の概要
単体的複体のpartitionabilityという概念に関して、基礎的な事項を
概観し、また、特にGarsia-Stanley予想に関連して、どのようなこと
をこれから考えていくとよいか、などについて議論したい。
Nコの文字からなるアルファベット {1,..,N} を使った Word の集合を
"自由モノイド"いい, その上の自己準同型写像を,
"階数Nの記号変換(Substitution)" と呼ぶ.
例えば、ランク3の記号変換 σ(1)=12,σ(2)=13,σ(3)=1 などがある.
記号変換から, フラクタル図形, タイリングを生成でき,
さらに力学系を導入することもできるのだが, そのような議論をする上で,
記号変換そのものについての研究も平行して行われている.
今回は, 逆写像をもつ記号変換に焦点を絞って話したい.
[参考文献]
[1] Zhi-Xiong WEN and Zhi-Ying WEN, Local isomorphisms of invertible substitutions,
C.R.Acad. Sci.Paris, t.318, Serie I, p.299-304(1994) .
[2] Zhi-Xiong WEN and Yi-Ping ZHANG, Some remarks on invertible substitutions
on three-letter alphabet, Chinese science bulletin, vol.44, Iss 19, p.1755-1760(1999).
[3] Hiromi EI and Shunji ITO, Decomposition theorem on invertible substitutions,
Osaka J. Math, vol.35, p.821-207(1998).
[4] Hiromi EI, Some properties of invertible substitutions of rank d,
and higher demensional substitutions, Osaka J. Math, vol.40, p.543-562(2003).
2次準割当問題(quadratic semiassignment problem)はスケジューリング問題
や施設配置問題などの定式化に現れるNP困難な最適化問題である．本研究では，
2次準割当問題の混合整数計画問題による定式化に対し，2次準割当多面体
を導入し、切除平面法の構築を目的として，多面体の考察を行う．2次準割当多面体は，
ブール2次多面体(boolean quadric polytope)を特殊ケースとして含み，また，2次割当多面体
(quadratic assignment poltope)の面に同型である．
本研究では、2次準割当多面体の次元を明らかにする．次に，この多面体の
アフィン包を定める等式系を決定する．また，ある妥当不等式の族が極大面を
定めるための必要十分条件を示す．さらに，この極大面を用いた切除平面法に
よって，ベンチマーク問題の最適解が容易に得られることを計算機実験によっ
て示す．
この研究は，藤江哲也(兵庫県立大学)，松井知己(中央大学)，
松浦史郎(東京大学)との共同研究であります．
暗号とは何か、どのように作られているのか、
以下の二種類の暗号を例に紹介します。
１．CryptMT: 高速に生成できる安全でない擬似乱数列に対して簡単な変換を
繰返し行うことで、安全性が高く高速で、かつ周期の長い擬似乱数列を
生成することができます。
２．FUBUKI: 共有鍵から１つの解読されにくい大きな暗号化関数を生成するのではなく、
高速な異なるタイプの変換を行なう関数を複数個用意し、共有鍵の情報によって
決まる組合せで文書を複数回変換して暗号化することで、
高速で変換の次元の高い暗号化関数を作ります。
これらの暗号は、広島大学・松本眞、斎藤睦夫、山形大学・西村拓士
と共同で現在ストリームサイファの新しい国際標準として応募しています。
マッチングとマトロイドインターセクションの共通の一般化として,
Cunningham and Geelen (1997) は独立パスマッチングという概念を
導入した. 独立パスマッチングについては,
多項式時間可解性や不等式表現の整数性など,
マッチングやマトロイドインターセクションがもつ
数々の性質が成り立つことが示されている.
本発表では, パスマッチングのさらなる一般化である
even factor について, 最大重み even factor アルゴリズムを
中心に紹介する.
最適停止問題の代表的な問題である古典的秘書問題と、
その拡張であるポアソン到着最良選択問題について
述べる。
今回、ポアソン過程のインテンシティが未知で、
自然数パラメータガンマ分布(アーラン分布)を
事前分布とする場合の最適停止規則を
無情報問題(応募者の順位のみが観測できる）と
完全情報問題(応募者の価値が観測できる)について
考える。
また、相対的ベストの応募者を採用している期間を
最大にすることを目的とした所有期間最大化問題についても
触れる予定である。
多次元割当問題は，割当問題の多次元への拡張であり，多ターゲット多センサ
監視システムにおけるデータ結合のモデルになっている．我々の扱う k 次元
割当問題の入力は，点が有理 d 次元空間に埋め込まれた完全 k 部グラフである．
辺重みは，両端点のユークリッド距離の平方で定まっているものとする．
目的は，点集合の k クリークへの分割で，分割を構成するクリークで誘導される
辺の重みの総和が最小になるものを見つけることである．
上記の k 次元割当問題は，多くの仮定にもかかわらず，k = 3, d >= 2 において
NP 困難である．本研究では，二次錐計画緩和と，丸め手続きを用いた
(5/2) - (3/k) 乱択近似解法を提案する．発表では，緩和問題の導出から，
乱択アルゴリズムの設計，近似率の算定に至るまで説明したい．
本研究は，松井知己 (中央大学) との共同研究である．
射影空間において自然にあらわれる凸概念とはいかなるものであるか？本研究では、
実ユークリッド空間における凸性を一般化し、実射影空間において、単純局所凸集合、
および、その一般化である局所凸集合の概念を導入した。ユークリッド空間の凸集合
に関する組合せ幾何でもっとも有名な定理の１つであるヘリーの定理が、実射影空間
の局所凸集合に関する一般化された定理として示される。これは、射影空間の双対性
を用いる計算幾何学の問題に応用されることが期待される。
戻る