組合せ数学セミナー
発表内容の概要
格子の最短ベクトル問題(Shortest Vector Problem, SVP)に対する高速なアルゴリズムを発表する。
N次元の実空間に線形独立なN本の整数ベクトルが与えられたときに、その整数結合全体が格子である。
格子の最短ベクトル問題とは、格子が与えられたときに、原点以外でもっとも原点に近い点を求めるという
問題である。その短いベクトルを求めるために、短い基底行列を求めるという方法が一般的である。
短いベクトルからなる基底を求めるアルゴリズムは、基底簡約アルゴリズムと呼ばれる。
基底簡約アルゴリズムとしては、Lenstra-Lenstra-Lovaszによる多項式時間アルゴリズムである
LLLアルゴリズム(1982)が有名である。
これは、最短ベクトルにたいする近似の精度が保証されている。
その後も基底簡約アルゴリズムは、進化してきた。近年はSchnorrによるBKZアルゴリズム、
およびその改良版がもっとも高速であると思われてきたが、
われわれのチーム(柏原賢二、獨協大学深瀬道晴)は、SchnorrのRSRアルゴリズムの手法を大幅に改良して、
より高速なアルゴリズムを開発することに成功した。
今回のコマゼミの発表では、最短ベクトル問題とはなにかということと、われわれの基底簡約アルゴリズムについて話す。
SVP challenge(http://www.latticechallenge.org/svp-challenge/)という最短ベクトル問題のサイトが公開されている。
そこで多くの研究者が競って問題に取り組んでいるが、われわれは、128次元の問題を解くことに成功した。
その取り組みについても話す。
有向グラフの描画の方法の一つに階層描画と呼ばれる描画法がある。
階層グラフとは階層描画を行う際に用いられるグラフ構造であり、
階層グラフG=(V,E)は、Vが空でない部分集合V1,V2,.....,Vhに分割
されており、任意の辺(v,w)∈E (v∈Vi,w∈Vj)はi≠jを満たしている。
辺e=(v,w) v∈Vi,w∈Vjにおいて、|i-j|を辺のスパンと呼び、スパンが２以上の辺を長辺と呼ぶ。
階層描画では一般に長辺上にダミー頂点と呼ばれる仮の頂点を設けることにより、
階層グラフのすべての辺のスパンを１にする操作が行われる。
本研究では、複数の長辺が同一のダミー頂点を共有することにより、ダミー頂点の数を減らす試
みを行った。ダミー頂点の共有化により、ダミー頂点の数と辺の本数が減らすことが期待できる
が、必ずしもダミー頂点数を最小とする共有化と辺の本数を最小とする共有化が一致するとは限
らない。ダミー頂点の数を最小にする共有化を求める問題と辺の本数を最小とする共有化を求め
る問題がそれぞれNP困難であることを示し、ダミー頂点の共有化アルゴリズムを紹介する。
また、本研究で取り組んでいる新しい階層描画アルゴリズムについて紹介する。
“トラベル・グルーポイド”とは、集合Vとその上の二項演算*のペア(V,*)で次の２つの
公理を満たすものである。
(t1) (u * v) * u = u (for all u,v in V),
(t2) if (u * v) * v = u, then u = v (for all u,v in V).
この概念は、2006年にL. Nebeskyによって導入された。
トラベル・グルーポイド(V,*)と単純無向グラフGに対し、
V(G) = V, E(G) = {{u,v} | u * v = v (u, v in V: distinct) }
となっている時、“(V,*)はG上にある”という。
本発表では、Nebeskyによるいくつかの結果を紹介するとともに、
発表者が最近得た結果について話す。より具体的には、
（１）無限グラフGに対し、その上にトラベル・グルーポイドが存在するための必要十分条件を与える。
（２）有限グラフが与えられた時に、その上にいくつトラベル・グルーポイドがあるかについて、
与えられたグラフの組合せ構造を用いた数え上げ公式を与える。
仁は、費用分担ゲームの解概念の一つであり、各提携の不満度をできるだけ小さく、かつ均等に
した配分方法である。
仁を求める解法としては、Kopelowitz [2] 、Maschler達 [3] が提案した線形計画問題を繰り返
し解く方法が広く知られている。
Kopelowitz [2] は、反復を高々n (プレイヤーの数) 回繰り返せば、仁が求められることを示し
た。
しかし、各反復における線形計画問題を解く効率的な解法は示されていなかった。これを受けて、
Hoang [1] は、Kopelowitz [2] 、Maschler達 [3] のアルゴリズムを改良し、許容提携の集合が
ある性質を満たす凸ゲームにおいて、仁を計算するための多項式時間アルゴリズムを与えた。
本研究では、さらに許容提携の集合がIntersecting familyである凸ゲームにおいて、Hoang [1]
の結果を用い、仁が多項式時間で求められることを示す。
[1] N. D. Hoang. Algorithmic Cost Allocation Games: Theory and Applications, PhD
Thesis, TU Berlin (2010).
[2] A. Kopelowitz. Computation of the kernels of simple games and the nucleolus of
n-person games.
Technical report, Research Program in Game Theory and Mathematical Economics, Hebrew
University, (1967).
[3] M. Maschler, B. Peleg, L. S. Shapley. Geometric properties of the kernel,
nucleolus, and related solution concepts, Mathematics of Operations Research, 4(4):
303-338 (1979).
並列計算機でシミュレーションをするときに,
各計算機で擬似乱数を発生させて用いることがあります.
しかし, 近くの現象を扱う計算機が全く同じ擬似乱数列を生成していると,
それによる偏りがおきてしまうので, 相関が大きい場所では
なるべく違う関数で生成された擬似乱数を用いる方が良い結果が得られます.
何種類かの関数しかないときに, どのように割り振れば良いでしょうか？
このような問題を解決するために，これまでグラフの分散彩色アルゴリズム
やその評価方法，存在条件についての研究を進めてきました．
本発表では，グラフを指定された色数で分散彩色する方法が何通りあるか
を表す分散彩色多項式についての研究を紹介します．
この講演の内容は論文
H. Tasaki, Antipodal sets in oriented real Grassmann manifolds, Internat.
J. Math. 24 no.8 (2013)
およびその後の進展の解説である。
コンパクト対称空間の二点が互いの点対称の不動点であるとき、
この二点を対蹠的という。
さらにコンパクト対称空間の部分集合の任意の二点が対蹠的であるとき、
その部分集合を対蹠的という。
これはChen-Naganoが導入した概念である。
{1, ..., n} の k 個の元からなる部分集合の全体を P_k(n) で表す。
P_k(n) の元 α, β に対して差集合の元の個数 #(α-β) が偶数になるとき、
α, β は対蹠的であるといい、部分集合 A ⊂ P_k(n) の任意の二元が
対蹠的であるときに、A を対蹠的という。
R^n 内の向きの付いた k 次元部分空間全体が成す有向実Grassmann多様体の
極大対蹠集合の等長変換全体の単位連結成分に関する合同類と、
P_k(n) の極大対蹠的部分集合の対称群 Sym(n) の作用による合同類は、
一対一に対応することがわかる。
これにより、有向実Grassmann多様体の極大対蹠集合の分類は、
P_k(n) の極大対蹠的部分集合の分類に帰着する。
k が 4 以下のときに P_k(n) の極大対蹠的部分集合を分類し、
この分類に現れる極大対蹠的部分集合の系列を拡張する。
さらにこれらの系列を利用して対蹠的部分集合のサイズを評価する。
３次元の空間に埋め込まれた円周のことを結び目という。結び目を平面に射影したものを
結び目射影図、その各交点に上下の情報を与えたものを結び目図式という。結び目図式は
結び目を一意に表す。
本講演ではまず、結び目理論を応用したゲームである「領域選択ゲーム(Region Select)」
を紹介する。領域選択ゲームとは次のようなゲームである。結び目射影図の各交点にランプ
が置かれており、射影図の線で囲まれた部分（領域）を選択するとその境界上のランプの
オン/オフが切り替わるというルールのもとで領域を選択していく。全てのランプを点灯さ
せることがゴールである。任意の結び目射影図、任意のランプの初期状態において、この
ゲームは必ずクリアできるということが、結び目図式の領域交差交換の研究によって示さ
れている。領域選択ゲームは河内明夫教授、岸本健吾氏と共同開発したゲームであり特許
出願中である。
次に、結び目図式のひずみ度の研究を応用したパズルについても紹介する。向き付けられ
た結び目図式の辺上に基点をとり、その基点から図式を１周たどると、各交点を上側と下
側の２回ずつ通過する。このうち先に下側を通過するような交差点のことをひずみ交差点
といい、ひずみ交差点の個数のことを、その基点におけるひずみ度という。結び目射影図
に対して、得られる全ての図式とひずみ度を考えることにより、ひずみ度行列という行列
を与える。この行列の性質を用いてできたパズルについて紹介する。
参考文献
[1] 河内明夫, 岸本健吾, 清水理佳, 「結び目理論とゲームー領域選択ゲームでみる数学
の世界―」, 朝倉書店 (2013)
トップに戻る