組合せ数学セミナー
発表内容の概要
マトロイドの独立集合族は単体的複体の構造を持ち、マトロイド複体という
名前でよく知られている。本発表では、nonpureな単体的複体においてマトロ
イド複体に準じるものを定義し、その性質を調べることを試みる。
円周上に１からｎまでの数を適当に並べ、その円周上のｋ連続和を考え、その最大値に注目する。
さらにｋ連続和の平均（= k(n+1)/2）との差を比べ、平均との差が一番小さくなる並べ方につい
て考える。
つまり、１からｎまでの数を円周上にどのように並べてもｋ連続和が平均 + x となるような最
大の x について考える。そのような x をmsum(ｎ,ｋ)と定める。
例えば、円周上に１から１３までの数を適当に並べると、どのように並べても３連続和が２３以
上になり、
２４にならないような並べ方が存在するので、msum(13,3)=2 となる。（この場合、平均 k(n+1)
/2 = 21 である。）
本講演では、適当なｎとｋに対するmsum(ｎ,ｋ)の値について紹介する。その系としてk=3, k=4,
k=6の場合のmsum(ｎ,ｋ)について紹介する。
（本講演は、栗本和季氏（京産大理学部４年）との共同研究に基づく。）
The center, the median and the centroid are classical notions that identify
central vertices in a tree. These can be defined as vertices where certain
functions defined on the vertex set of a tree are minimized. We define a
broader class of functions, called convex and quasiconvex functions,
on the vertex set of a tree. We present several examples of such functions
which arise from matrices associated with the tree such as the distance matrix
and the Laplacian matrix.
RAID（Redundant Arrays of Independent Disks）は、複数のディスクを並列に扱い、処理速度
と安全性を高める技術である。読み込み・書き込みを行うディスクの順序を効率良く配置するこ
とが重要である。グラフの頂点をディスクに、グラフの辺のラベルをRAIDのアクセス順序として、
数理モデル化できる。
正方形RAIDを構成するために、任意の正整数h,tに対して、上側頂点と下側頂点の個数が同じと
なるような二部グラフH(h;t)を定義する。二部グラフH(h;t)と同型なグラフを合成すると、完全
二部グラフになる。サイクリックになるように$H(h;t)$の辺の順序付けを与え、h=1,2,3,4の場
合の無限系列の構成例を与えた。さらに、一般化した任意の正整数h,tの場合について、無限系
列の構成法を与える。
二部グラフH(h;t)は上下の頂点数が同じなので、これを拡張して上下の頂点数が異なる二部グラ
フH(h,k;t)を定義する。さらに、h=1の場合の無限系列の構成法を与える。このとき、H(h,k;t)
と同型なグラフを合成しても、完全二部グラフにはならない。また、対応するRAIDは正方形では
なく川の流れのような階段状になる。
グラフがある性質Pを満たすための十分条件として，性質Pに支障をきたす部分構造の禁止を考え
ることは自然である．
そのような禁止部分グラフ条件は性質Pの本質を表すと見なされるため，グラフ理論において幅
広く研究されており，関連する有名な定理や予想が数多く知られている．
特にある性質Pの十分条件となる禁止部分グラフ条件を決定することは重要である．
しかしある性質Pを保証する禁止部分グラフ条件が複数存在する場合，その各々の証明は似通う
ことが多いため，禁止部分グラフ条件の決定は繁雑になりがちである．
そこで本講演ではclaw（完全２部グラフで，部集合のサイズが1と3となるもの）を中心としたい
くつかの禁止部分グラフ条件の比較を行い，その強弱や同値性を議論することで，禁止部分グラ
フ条件の問題を再考する．
通常の最適化問題では制約はすべて満たされる必要がある．一方で，いくつかの
問題においてはすべての制約を満たす必要がない場合もある．
このような文脈から， 制約のうち特定の本数は満たさなくてもよいというモデ
ルは，線形計画，施設配置，クラスタリング,セットカバー問題等，さまざま問
題で研究されている．本研究では，線形計画法においてk本の制約は満たさなく
てもよいという問題の特殊ケースである，Covering-type k-violation linear
programに対して精度の保証がある近似アルゴリズムを与える．
基底簡約問題に対する比較的シンプルで高速なアルゴリズムを発表する。
N次元の線形空間に線形独立なN本の整数ベクトルが与えられたときに、その整数結合全体が格子
である。
格子の最短ベクトル問題とは、格子が与えられたときに、原点以外でもっとも原点に近い点を求
めるという問題である。
その短いベクトルを求めるために、基底簡約するというアプローチが主流である。
これまで、基底簡約アルゴリズムとしては、深瀬道晴氏、照屋唯紀氏との共同研究を通じて、
SchnorrのRSRアルゴリズムの手法を大幅に改良した高速なアルゴリズムを発表してきた。
しかし、多くの工夫を取り入れた為に、プログラムが複雑化し、アルゴリズムが理解しづらくなっ
てしまった。
また高速化にどの部分が効いているかもわかりづらく、またファイルをたくさん生成する為に、
気軽に実行できなかった。
今回は、今までのプログラムのエッセンスを取り入れた、シンプルだけど、伝統的な手法よりも
高速なアルゴリズムを発表する。
具体的には、ENUMを利用した格子ベクトル生成を行い、ベクトル更新条件としては閾値法を採用
して、基底の自乗和を下げている。
マトロイドパリティ問題はマッチング問題とマトロイド交叉問題の共通の一般化として1970年代
に導入された問題である。この問題は一般のマトロイドにおいては指数回のオラクル呼び出しを
必要とするが、線形マトロイド上の問題に対してはLovasz (1980)が多項式時間アルゴリズムを
与えている。マッチングアルゴリズムやマトロイド交叉アルゴリズムは重み付き問題へ拡張がな
されているのに対して、重み付きの線形マトロイドパリティ問題に対する多項式時間アルゴリズ
ムは30年以上知られていなかった。本研究では、重み付き線形マトロイドパリティ問題に対して
初の多項式時間アルゴリズムを与える。本研究は東京大学の岩田覚教授との共同研究である。
トップに戻る