組合せ数学セミナー
発表内容の概要
1996年Kleinbergによって提案された1品種1パス流(unsplittable flow)
問題は, 古典的多品種流(multicommodity flow)問題の
拡張で, 各品種について需要を満たすのに使うことのできるパスは1本だけである.
さらに, 1品種1パス流問題は容量付きネットワーク上での辺素パス
(edge disjoint paths)問題と
考えることもでき, 高バンド幅ネットワークの接続要求問題, 光ネットワーク,
スケジューリング問題, VLSIの配線問題などの基本的モデルとして用いられている.
1品種1パス流問題の実行可能性判定問題はNP-完全である.
したがって, 研究の主眼は様々なバリエーションの近似アルゴリズムの構築となる.
1996年にKleinbergが1始点(single-source)の場合の
1品種1パス流最小費用流問題の過密度および費用に関して定数近似を実現する
アルゴリズムを提案して以来,
Kolliopoulos-Steinが1997, 1999年に, Dinitz-Garg-Goemansが1998年に,
1始点の場合についてアルゴリズムを発展させてきた.
多始点(multiple-source)の場合に関しては, Kleinbergの結果を除いて,
過密度や最小費用流問題に関する結果を見つけることができなかった.
今回は, 多始点の場合の1品種1パス流における最小費用流問題を考える.
まず, Kolliopoulos-Steinが1997年および1999年に提案した1始点の場合に
適用できるアルゴリズムを多始点の場合に拡張することによって
数種類のアルゴリズムを得た. とくに任意のグラフ, 始点数が$c$のときに
過密度$c+2$, 費用 2近似のアルゴリズムを得ることができた.
これらのアルゴリズムは, $c$が品種の数に比べて比較的小さいときの方が
より良い近似性能を示す.
それから, Raghavan-Thompsonによって発展した線形計画緩和とランダマイズド
ラウンディングを組み合わせた方法に基づいたアルゴリズムおよび
貪欲手法に基づいた新しいアルゴリズムについて, 計算機実験を用いて
近似性能を評価した.
Poset の bound graph とは, 頂点集合を poset の要素とし,
2点間に共通の辺の存在する条件を共通上界や共通下界の存在によって
定義することで得られる graph で, 1982年に F.R.McMorris と
T.Zaslavsky によって導入されました.
本発表では各 bound graph の性質をお話しした後,
いくつかの関連した研究について紹介します。
最適施設問題の一つであるハブ空港配置問題に対する
アプローチとして、従来はヒューリスティックによるものと
線形計画緩和によるものがありました。
本発表では、この問題に対し線形計画緩和をよりも強力といわれ
最近特に注目を集めている半正定値計画緩和を用いた解法と
その結果を紹介します。
単体的複体のshellabilityというのは組合せ的な条件において
単体的複体を構成することが可能かどうかを問う概念である。
今回の発表では2次元の単体的複体がshellableな細分を
持ち得るための条件について考えてみる。
しかし、今回の話の目的は実はR. Formanによる離散モース理論
を紹介することである。前半に2次元単体的複体がshellableな細
分を持つための必要十分条件を紹介した後、後半で簡単に離散モ
ース理論の入門的な紹介をしたい。
トーリックイデアルのグレブナ基底は，代数幾何学的にも重要な
概念であるが，その離散性を通じて整数計画や数え上げなどの組
合せ的な問題にも応用されている．
一方，Gel'fand-Kapranov-Zelevinsky は，行列に対して GKZ-超
幾何系と呼ばれる偏微分方程式系を定義し，トーリック多様体と
の関連や組合せ的な性質を調べた．GKZ-超幾何系は Gauss の超幾
何方程式などの重要な超幾何方程式を含んでおり，その組合せ的
な性質とともに，トーリックイデアルのグレブナ基底を用いたア
ルゴリズムなどが近年注目されている．
本発表では，整数計画を通じてトーリックイデアルのグレブナ基
底を定義し，グレブナ基底を用いて GKZ-超幾何系の解の次元が計
算できる例を紹介する．(サーベイ的な内容になると思います)
Ｍ凸関数は, 整数格子点上で定義された関数のクラスとして,
1996年に室田により提案された概念である.
その後の研究により, Ｍ凸関数は離散的凸性として相応しい諸性質を満たすとともに,
貪欲算法（降下法）により最小解が求められる, ということが示された.
本発表では, 離散的な凸関数であるＭ凸関数の最小化問題に対し,
スケーリング技法を用いた効率的なアルゴリズムを提案する.
J.M. Bilbao をはじめとするセビリア大学のゲーム理論グループおよび
P.H. Edelman の行なっている，凸幾何上の協力ゲーム理論に関する研究 [1]
の紹介をします．
古典的な協力ゲームでは，プレイヤーの提携としてはプレイヤー全体の任意の
部分集合を許していました．しかし，実際にはそのような状況は稀であり，政
治的・文化的・地理的状況により提携として許されないようなプレイヤーの部
分集合もあります．そのような状況をモデル化したものとして，Bilbao ら，
および，Edelman は凸幾何上の協力ゲームを提案し，その性質を調べています．
凸幾何とは反交換公理を満たす閉包空間として定義され，アンチマトロイドの
双対としても認識されています．凸幾何上のゲームについて今までに様々な結
果が得られています．本発表では次の中の一つ，あるいは複数に絞ってその内
容を紹介させていただきます．
なお，協力ゲーム理論についての簡単なところからはじめるつもりですし，私
自身もあまり細かいことは知らないので，肩の力を抜いて楽しんでいただけた
ら嬉しいです．
(1) 凸幾何上のシャープレイ値について
シャープレイ値はそのゲームにおける各プレイヤーの貢献度と考える こ
とができます．そのシャープレイ値を凸幾何上にいかに拡張するか，とい
う話．
(2) 凸幾何上の重み付き投票ゲームについて
最近，Matsui-Matsui の論文 [2] ，あるいは松井知己さんのWeb page
[3] で話題になっている重み付き投票ゲームは協力ゲームとして定式化で
きます．古典的な重み付き投票ゲームを凸幾何上に拡張し，その投票力指
数を実際に欧州連合をケースとして計算する，というお話．
(3) 凸幾何上のコア，Weber集合について
協力ゲームの解概念としてコア，Weber集合というものが知られていて，
それらは凸多面体を構成しています．古典的な協力ゲームの場合は，ゲー
ムが凸 (すなわち，優モジュラ) である場合コアとWeber集合が一致しま
す．しかし，凸幾何上のゲームの場合はコアとWeber集合の間に包含関係
さえなくなってしまうことがあり，では，包含関係があるのはどういうゲー
ムのときなのかを定める，というお話．
参考文献
[1] J.M. Bilbao, Cooperative games on combinatorial structures, Kluwer
Academic Publishers, Boston-Dordrecht-London, 2000.
[2] T. Matsui and Y. Matsui, A Survey of Algorithms for Calculating
Power Indices of Weighted Majority Games, Journal of the
Operations Research Society of Japan, Vol. 43, No. 1, 2000,
pp. 71--86.
[3] 松井知己，Power Indices of Voting Games (投票ゲーム(選挙)の投票力指数),
http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/voting/voting.html .
Arrow の一般可能性定理は、公共選択論における重要な定理であり、
合理的な社会選択関数が独裁者を導く事を示している。本発表では
一般可能性定理の証明を解説する。また、一般可能性定理の妥当性
の議論として、Sen の反例、Black の定理等の紹介を行なう。
上記に耳慣れない言葉が沢山ある方でも、一から全部説明します
ので、心配せずにご出席下さい。
凸幾何とアンチマトロイドの概念を、歴史的順序をふまえて
説明する。凸幾何は、ある束をなす集合族で、凸性の組み合わせ化、
もしくは離散化として研究が始まった。
一方、アンチマトロイドは、グラフなどの組み合わせ的対象の上で
のシェリングから定義されるものとしてらえることができる。
凸幾何とアンチマトロイドは、アンチマトロイドの元の補集合の
全体は凸幾何をなしかつその逆も成立するという意味で、まったく
同値な概念である。
まず、これまでに文献に現れている実例をなるべくたくさん集めて
説明する。続いて、アンチマトロイドのパスとサーキットの概念を
導入する。このパスとサーキットは、互いにブロッカーになることが
知られている。一般にこれらは、パックしないので、これらが
パックするアンチマトロイドのクラスとそうでないものを分類して
考察する。
以下に、資料が Postscript file として添付してあります。
ご利用下さい。
資料 (Postscript file)
実在する物体の形状をメッシュ化する場合、（3次元スキャナなどで）
物体表面の点を多数サンプリングしその頂点列を入力としてメッシュを
形成する方法をとることが多い。このとき、物体のメッシュは shellability
を満たすことが求められる。
つまり、shellability はメッシュにおいて非常に基本的な性質となっている。
この shellability は純な単体的複体の上に定義されている性質である。
今回は「ある単体的複体が与えられた時に、shellable であるかどうかを
判定するアルゴリズム」について考えた。
shellability 判定では、特に効率が良い判定方法もなく、通常は(単体的
複体を形成する facet の数 = ) #f の階乗時間を要することが知られている。
そこで、単体的複体の性質を表すベクトルの1つである h-vector を用いる
ことにより、d次元単体的複体の場合、h-vector の最大項 (= h_(d+1)) の
階乗分だけ判定計算を簡単化することができ、(#f) ! / h_(d+1) ! 計算時間で
判定可能であることを示す。
平面的グラフG=(V,E)と、平面上に与えられた|V|個の点の集合P
に対し、Gの平面への埋め込みでVをPの異なる点に写し
Eを線分に写すものを
GからPへの直線埋め込み
と呼んでいます。まずは一連の研究の発端となった
rooted treeの直線埋め込み問題から始め、拡張型である
forestの強直線埋め込み、弱直線埋め込みの問題について、
これまでに解決したこと、残る未解決の問題を順に説明していきます。
特別な知識は一切不要ですのでどうぞ気楽に聴いて下さい。
Union-closed sets conjecture
（Franklの予想）とは有限集合Ｘ上の有限集合族Ｆが
和に関して閉じている、
Ａ, Ｂ∈Ｆ⇒Ａ∪Ｂ∈Ｆ
ときには必ず点ｘ∈Ｘが存在して
|{Ａ∈Ｆ：ｘ∈Ａ}|≧|Ｆ|/２
となる予想である。ただしＦ≠φ
和で関する集合族は半束になるために束論から
アプローチができる。例えば、条件を付加して
証明を行うなど。
今回の発表ではまだ未解決であるセミモデュラー束
についてどこまで分かっているかを扱う。また、
この予想について現在まで知られていることを
総まとめしたい。
トップに戻る