組合せ数学セミナー
発表内容の概要
事前には、「Independence systemについて」という題で発表するという
ふうにいってしまいましたが、この題で申し込んだときには、なにを発表するか
あんまり決めてなかったので、抽象的な題にしてしまいました。
結局、ここ1年研究してきた整基多面体の分割の話をすることにしました。
整基多面体というのは、劣モデュラー関数に付随する多面体の一つです。
それを多面体分割しようという話です。
概要：
有限束に「不足数」という値を導入することで、この値から有限束
の形がどのように決まるのか、を調べることが目標です。分配束、
相対相補束の場合はきれいな性質が得られています。
１．束論の紹介：
「束」といえば「bundle」、「lattice」といえば「格子」と
思われてしまうぐらい、肩身の狭い思いをしている束論の
基本的な事柄を説明致します。したがって予備知識は不要です。
２．Union-Closed Sets Conjecture：
超グラフの未解決問題(たぶん)です。フランクルの予想とも
呼ばれています。有限束は特殊な超グラフであるので、束論から
この予想へアプローチすることができます。
３．不足数
不足数が正であるならば、ある定数Ｃが存在して
束のサイズ ≦ Ｃ×不足数
となるだろうか？という問題を考えます。また等号を満たす
ものは本質的に何種類に限るかということも併せて考えます。
分配束、相対相補束についてはきれいな形が得られています。
Monge 行列をコスト行列にもつ輸送問題に北西隅法というある種の貪欲算法が
有効であるということは良く知られています。Faigle and Kern [2] は、劣モ
ジュラ関数を用いて定義される多面体上での双対貪欲算法を導入し、Monge の
貪欲算法とポリマトロイドに対する貪欲算法を、同時に一般化しています。
(ここでいう多面体は通常の意味での劣モジュラ多面体とは異なります。)
Faigle and Kern の貪欲算法の適用可能性は、さらにKr\"uger [3] によって
一般化されました。
本発表では、Kr\"uger [3] の意味での劣モジュラ関数/多面体に対する双対
貪欲算法を説明し、最近得られた成果 [1] について話をします。
参考文献:
[1] K. Ando: The greedy algorithm for a class of lattice polyhedra and its
consequences. Discussion Paper No. 830, Institute of Policy and Planning
Sciences, University of Tsukuba (August 1999).
[2] U. Faigle and W. Kern: Submodular linear programs on forests.
Mathematical Programming 72 (1996) 195--206.
[3] U. Kr\"uger: Structural aspects of ordered polymatroids. Reports on
Optimization and Stochastics 97-44, Fachbereich Mathematik und Imformatik,
Martin-Luther-Universit\"at Halle-Wittenberg, Germany, 1997.
(to appear in Discrete Applied Mathematics).
大規模な文書類似判定問題を背景に，"Min-Wise Independence" なる概念が
[n]={1,...,n} 上の置換の集合 S_n の部分集合に対して，Broder et.al. に
より1998年に定義されました．
S_n の部分集合 F から置換 \pi をランダムかつ一様にとったとき，任意の
[n] の部分集合 X および各 x \in X に対し，
Prob_{\pi \in F} [\pi(x) = min \pi(X)] = 1/card(X)
が成立するとき，F は Exactly Min-Wise Independent Permutation Familyと
よばれます．このような F にたいして，lcm(n,n-1,...,1) が card(F) の下
界であることが Broder. et.al. により示されていました．(lcm は最小公倍数)
本発表では，この下界を達成する F を具体的に構成します．また，その構
成を一般化し，任意の Exactly Min-Wise Independent Permutation Family
を構成する戦略を示します．
２元（分割）表の数え上げ問題は，近年，計算代数，代数的
組合せ論を中心として方法論が発展し，応用上も，統計学に
おける分割表解析などで基本的な役割を担っています．
今回の発表では，文献 [1], [2], [3], [4] に基づいて
１．２元表の集合上のメトロポリスウォーク
２．対称群のコセットによる超幾何乱数の生成法
３．対称式の基底変換と総数計算
を紹介します．１は，石関さん発表（１２月１３日）の
「グラフのトーリックイデアルのグレブナ基底の解析」
とも関係が深いですが，トーリックイデアルを導入せずに，
メトロポリス法によって２元表を頂点とするグラフを構成し，
ランダムウォークを考えます ([2], [4])．また，文献 [1]
には，上の２，３を含め２元表の群論的な解釈がまとめられて
います．文献 [1] の結果を利用して，総数計算の具体的な方法
を示し，いくつかの２元表に関して，総数の正確な値と近似値
（カイ二乗近似，正規近似）とを比較します([3])．
参考文献
[1] Diaconis, P. and Gangolli, A. (1995).
Rectangular arrays with fixed margins,
In Discrete Probability and Algorithms (D. Aldous et al., eds.),
15--41, Springer, New York.
[2] Diaconis, P. and Sturmfels, B. (1998).
Algebraic algorithms for sampling from conditional distributions,
Ann. Statist., 26, 363--397.
[3] 橋口博樹 (1999).
２元分割表の総数計算について,
日本計算機統計学会 第１３回シンポジウム論文集, 94--97.
[4] 中川重和 (1999).
分割表の数え上げと MCMC,
日本計算機統計学会 第１３回シンポジウム論文集, 98--99.
巡回セールスマン問題(TSP)は与えられた重み付き完全有向グラフの長さ最小のハ
ミルトン閉路をみつける問題です。
TSPはNP困難に属する有名な問題の1つであり、近似解を得るためのさまざまな手
法が研究されています。その一方、多項式時間で最適解が得られるためには頂点
間の距離がどんな条件をみたしていればよいかといった研究もされています(例え
ば[1])。この発表では後者について考えます。例えば、11/8の安藤さんの講演に
も登場したMonge行列についてもTSPの最適解が多項式時間で解けることが知られ
ています[2]。
今回の発表ではこれまでに自分がやってきたことをMonge性も交えて話してみた
いと思っています。
参考文献
[1] R. E. Burkard, V. G. De\v{\i}neko, R. van Dal, J. A. A. van der Veen
and G. J. Woeginger, Well-Solvable Special Cases of the TSP: A Survey,
SIAM Review 40, 1998, pp.496-546.
[2] J. K. Park, A special case of the $n$-vertex traveling-salesman
problem that can be solved in $O(n)$ time, Information Processing
Letters 40, 1991, pp.247-254.
私の専門は、アルゴリズムの高速化です。
特に、計算時間が入力の多項式に比例するような
アルゴリズムに対しての高速化に興味があります.
計算量的な観点からは、上記の「多項式」の最大次数が
計算速度に大きく関わってきます. そこで、この最大次数を
いかにして小さくするようなアルゴリズムを設計するか、
というのが、高速化をする上での目標になるわけです.
また、アルゴリズムに対して、上記の最大次数がどれくらいになるかを
、如何に算定するか、というのも一つの重要な研究です.
今回の話は、再帰型、つまり、ある問題を、いくつかの子問題を
再帰的に解くことによって解く、というタイプのアルゴリズム
について、その計算時間の算定方法を１つ、提案します.
あわせて、その算定を行うときに、あると便利であろうと思われる
補題を幾つか紹介します.
算定法のほかに、アルゴリズムの設計に関しても話をします.
この算定法を用いた場合に、効率良く最大次数が押さえられる
ようなアルゴリズムの設計方法、及び、この設計方法に
基づいて高速化されたアルゴリズムの紹介をします.
近年、トーリックイデアルを通してグレブナ基底を組合せ論の計算困難な問題に
適用する研究が行われています。(例えば [1]) その基礎研究として、グラフの
トーリックイデアルについて解析し、それを組合せ論の問題に応用する研究も行
われています。(例えば [2])
今回の発表では、まずグレブナ基底やトーリックイデアルについてお話します。
(ここが時間がかかりそうなのですが...)
無向完全グラフ、無向完全二部グラフ、無閉路トーナメントグラフに対して、あるグ
レブナ基底がグラフの言葉で表現できることを示します。また、無閉路トーナメ
ントグラフについて、グレブナ基底の次数や要素数の解析を行います。さらに、
(時間があれば)それぞれのグラフについて、組合せ論の問題への適用を考えます。
(先日の橋口さんの発表と絡めて話せればと思っています)
参考文献：
[1] P. Conti and C. Traverso. Buchberber Algorithm and Integer Programming.
Proceedings AAECC-9, Springer, LNCS 539 (1991), pp. 130-139.
[2] J. A. de Loera, B. Sturmfels and R. R. Thomas. Gr{\"o}bner Bases and
Triangulations of the Second Hypersimplex. Combinatorica 15 (1995), pp. 409-424.
単体的複体に関してshellabilityという概念
があるが、これは単体的複体の再帰的な分割
を保証するものとみることができ、このshellability
およびその類似概念を総称して「組合せ分割」
と呼んでいる。
今回の話では、3次元の球面や球体の三角形分
割の場合を取り上げ、組合せ分割が不可能な
ものをどうやって作るか(示すか)を紹介する。
The enumeration of all vertices of a bounded
polytope given by its facets is a classical
problem in computational geometry. We present
some preliminary results and ideas to
practically compute some highly degenerate
polytopes using their geometric and
combinatorial properties
Joint work with Komei FUKUDA (ETH Zurich)
and Masanori SATO （東工大）
向きづけ可能な曲面と同相な２-単体複体において、その各１-単体に[0,2π)の
範囲で重みを与えます。そして、この１-単体を対角線、これを含む２つの２-単
体を四角形と見て、対角線の端点にならない二つの頂点についての内角の和を先
の重みとします。この条件下で決まる単体複体の幾何構造はどのようなものか、
という問題を考えます。
I.Rivinは[1]において、線形計画問題の手法を利用し、この単体複体が相似構造
を持つ必要十分条件を与えました。
一方[2]において、相似構造が存在すればそれらの中でcone singularityを持つ
完備なユークリッド構造が唯一存在することを、双曲空間上で各単体の無限遠点
からの錐の体積を利用することで示しました。
今回の発表ではこれらの手法を紹介し、考えられる応用について話をしたいと思
っています。
参考文献：
[1]I.Rivin. Combinatorial optimization in geometry, preprint 1999.
[2]I.Rivin. Euclidean structures on simplicial surfaces and hyperbolic
volume, Annals of mathematics 139(3),1994.
トップに戻る