組合せ数学セミナー
発表内容の概要

4/9(月): 八森正泰(JST・ERATO)
「Kneserグラフの彩色数」

今回は，トポロジー的組合せ論の古典的結果の紹介をしたい．
  Kneserグラフ K_{n:m} とは，集合 {1, ...,n} のサイズmの各部
分集合を頂点と考え，二つの部分集合が互いに交わらない時にその
頂点同士を結んで得られるグラフのことである．例えば K_{n:1} は
完全グラフ K_n であり，K_{5:2} はPetersenグラフとなる．
  このKneserグラフ K_{2n+k:n} は，彩色数が k+2 以下であることは
簡単に分かるが，k+1 色では彩色できないということは1956年に
Kneserによって予想されて後，1978年になってLovaszによって，よ
うやく証明されることとなった．
  今回は，このLovaszによるKneser予想の解決をWalker(1983)の方
法に(一部省略しながら)従って紹介してみたい．

Reference:
L.Lovasz, Kneser's conjecture, chromatic number, and homotopy,
  J. Combin. Theory Ser. A 25(1978), 319-324.
J.W. Walker, From graphs to ortholattices and equivariant maps,
  J. Combin. Theory Ser. B 35(1983), 171-192.

4/16(月): 伊藤雅史(東京理科大・工・経営工学)
「グレブナ基底を用いた巡回セールスマン問題の解法」

1991年, トーリックイデアルのグレブナ基底を用いた整数計画問題の解法が
Conti, Traversoによって提案された. 以来, これを基礎として, 整数および
線形計画問題のさまざまな性質を記述する興味深い研究がなされている. 
しかしながら, グレブナ基底の計算は多大な時間と記憶容量を必要とする
ことが知られており, それゆえにConti, Traversoのアルゴリズムは実用的
であるとはいえない. 
そこで本発表では緩和法や分枝限定法などの,  整数計画問題に対する良く
知られたアプローチと組合せることの利点について, 巡回セールスマン問題
を取り上げて説明する. 

4/23(月): 平林隆一(東京理科大・工・経営工学)
「順序複体の shellability を極大鎖グラフを用いて判定することについて」

1980年,に Bjorner が順序複体（半順序複体の鎖からなる単体的複体）に
が shellable となる十分条件を見つけた．これは，多項式時間で判定できる
ものではあったが，条件としては強すぎ，shellable でも Bjorner の条件を
みたさないものが沢山存在する．
　そこで，1997年に　Ikebe,HIrabayashi は，順序複体から誘導される
極大鎖グラフを用いて，順序複体が shellable かどうかを判定する必要
条件を導いた．これは，極大鎖グラフが本質的サイクルを含むと順序複体
は shellable ではないというものである．しかし，この必要条件が成り立つ
かどうかをを実際に判定する方法はその時点では未解決であった．
　また，上の必要条件が十分条件でもあるかどうかということも未解決
であった．今回は，この２点について，八森氏のアドバイス／叱咤激励（？）
によって，何とか答えることができたので，報告する．

なお，本報告は伊藤美保（前Ｍ２）との共同研究です．

5/7(月): 安藤和敏(筑波大・社会工学)
「凸幾何の端点演算子による特徴付けについて」

凸幾何の端点演算子は, 経済学の社会的選択理論における選択関数の Path
Independence という性質によって特徴付けられることが, Koshevoy によって明
らかにされた. これは, 経済学と離散幾何学という関係ないように見える二つの
研究分野を結びつける画期的な結果であると思われる. 
  凸幾何については, このCOMAゼミでも岡本さんたちによって何回は話されている
話題ですが, 今回は上記の Koshevoy の結果を中心に, 凸幾何/アラインメント
の端点演算子の性質を整理してながら, 新しい結果も織り交ぜて話をします. 

5/14(月): 松井泰子(東海大・理・情報数理)
「分割表とその組合せ的性質」

分割表は、統計データを分類するのに持ちいられる表です。
セミナーでは、分割表に関する論文紹介をします。

5/21(月): 岩田覚(東大・情報理工学・数理情報)
「劣モジュラ関数最小化の完全に組合せ的なアルゴリズム」

概要: 劣モジュラ関数の最小値を求める組合せ的な強多項式時間
アルゴリズムが, 1999年夏に, Schrijver と Iwata, Fleischer, 
Fujishige によって独立に与えられた。これらのアルゴリズムは, 
ともに乗除演算を用いるという点で, 完全に組合せ的ではないと
いうことが指摘されていた. 本発表では, 後者のアルゴリズムを
変形することによって, 加減算と大小比較のみを用いた完全に
組合せ的な強多項式時間アルゴリズムを発表する。

5/28(月): 宮本裕一郎(東京商船大・流通情報工学)
「在庫配送計画とその周辺」

配送計画問題とは，限られた運び手により要領よく品物を配送するためのルートを計画す
る問題です．
運び手が1人で特に制約がない場合には巡回セールスマン問題と同じです．
品物の在庫状況を把握しながら，どのお客さんを訪れるのかということも考慮し，多期間
にわたる配送ルートを計画する問題が在庫配送計画問題です．
今回は，お客さんの例として（人じゃないけれど）自動販売機を例とした話をしたいと思
います．
最新のアルゴリズムを紹介するという話ではありません．
組合せに関する研究が実社会でも大変役に立っているという話です．

6/4(月): 竹内史比古(国立国際医療センター研究所)
「疑似３角形分割（pseudo-triangulations）」

平面の点配置が与えられたとき、その凸包を（全ての点を使って）
３角形に分けるのが、３角形分割である。これに対して、疑似３角
形分割という拡張がある。内角がπ未満の頂点が３つある（凸でな
くても良い）多角形を、疑似３角形とよぶ。凸包の疑似３角形への
分割が、疑似３角形分割になる。

疑似３角形分割は、ときとして３角形分割よりも良い性質を持ち、
近年、計算幾何の分野で、visibility, ray shooting, robot
motion planning などに応用されている。

n 点からなる点配置に対して、最小数である n-2 個の疑似３角形
分割への分割を、最小疑似３角形分割とよぶ。この発表では、最小
疑似３角形分割の次数（一つの頂点を共有している辺の数）のタイ
トな上限が５であることを示す [1,2]。また、最小疑似３角形分割
の robot arm motion planning への応用も紹介する [3]。

[1] Lutz Kettner, Andrea Mantler, Jack Snoeyink, Bettina
  Speckmann, Fumihiko Takeuchi,
 Bounded-degree pseudo-triangulations of points,
 in: Proc. 17th Europ. Workshop Comp. Geom., 19--22, 2001.
 http://cs.smith.edu/~streinu/Workshops/kmsst.pdf

[2] Lutz Kettner, David Kirkpatrick, Bettina Speckmann,
 Tight degree bounds for pseudo-triangulations of points,
 manuscript.

[3] Ileana Streinu,
 A combinatorial approach to planar non-colliding robot arm
  motion planning,
 in: Proc. 41st Annual Symposium on Foundations of Computer
  Science (FOCS), 443--453, 2000.
 http://cs.smith.edu/~streinu/Papers/motion.ps.gz

6/11(月): 宇野毅明(国立情報学研究所)
「極小集合被覆列挙問題の実践的な解法」

集合被覆とは、台集合 $E$ 上の部分集合族 $F \subseteq 2^E$
に対して、$F$ の部分集合 $S$ で、台集合の任意の要素が $S$ 中の
ある要素に含まれる、すなわち、$E = \{ x|x \in T \in S \}$ となるようなもの
のことです。で、このような集合被覆の中で、極小なものを全列挙しましょ、
てのが目的です。
が、いろいろと難しいことがありまして、どうも世の中うまくいってないんです。
計算量的に一番早いものは、集合被覆1個あたりの計算時間が O(|E|^{log |E|})
てな感じになってました。たしか。
計算量的に、1個あたり $|E|$ の多項式時間で解けるかどーかはオープンです。
てなわけで、難しいところは避けといて、実践的に早いものを作ってみました。
どうやって作るかは当日まで秘密。

ではではお楽しみに。

6/18(月): 宮沢裕之(東大・工・計数工学)
「重み付き区間選択問題（WISP）に対する新たなランダマイズド解法」

概要：
重み付き区間選択問題(Weighted Interval Selection Problem, WISP)とは、
実数軸上の重み付き区間の集合が与えられたときに、
重みの総和が最大になるような部分集合を選ぶ問題である。
ただし、部分集合内の任意の区間対は交わりをもってはならない。
実数軸を時間軸と考え、区間を機械の使用時間帯とすれば、
WISPは１機械スケジューリング問題の一種となり、
ＯＳの資源割り当て問題など応用上重要な意味をもつ。

本研究ではオンライン設定のWISPについて議論する。
各区間は逐次的に提示され、その場で採用／棄却を判断せねばならない。
将来提示される入力に関する情報が無いため
一般にオンライン設定の問題は原問題よりも難しく、
必ずしも最適解が求まるとは限らない。
そこで、解法を評価する上で解法の近似精度が重要となる。
すべての区間が同一の長さをもつ場合、
最適な決定的解法の近似精度は1/4であり、
それより良いランダマイズド解法が存在するか否かは長年の未解決問題であった。

本発表では、オンライン設定のWISPに対する新しいランダマイズド解法を提案し、
それがWISPのある特定のクラスに対して近似精度1/3を達成できることを証明する。
これは、上記の未解決問題に対する最初の理論的結果である。

6/25(月): 小田芳彰(島根大・総合理工・数理情報システム)
「ネックレス条件と巡回セールスマン問題」

この発表では、次の論文紹介をしたいと思います。

Testing the Necklace Condition for Shortest Tours and Optimal Factors in
the Plane, by H.Edelsbrunner, G.Rote and E.Welzl
Theoretical Computer Science 66(1989) 157-180

これまで私は巡回セールスマン問題が多項式時間で解けるような条件を考えてき
ました。その際対称性を特に仮定しないものが中心でしたが、ここでは平面上の
点配置Pを考えます。つまり対称性も三角不等式も仮定します。

Pの巡回路をTとし、Pの各点を中心とするdiskを作ったとき、2つのdiskが交わっ
ているならばその中心同士はT上で隣接していて、交わっていないときには隣接
していないようなTをnecklace tourとよびます。necklace tourを持つ点配置Pを
necklace条件をみたすということにします。

ここでは与えられた点配置Pに対しnecklace tourが存在するか判定し、存在す
ればその巡回路を出力するような多項式時間アルゴリズムを紹介します。この
アルゴリズムにより、与えられた点配置がnecklace条件をみたすならばTSPの
最適解が多項式時間で見つかるという仕組みです。 

点を中心としたdiskを考えるので、以前COMAセミのMLで話題になったコイングラ
フと雰囲気がよく似ていると思い、この論文を紹介しようと思ったのですが、こ
れらの関係についてはまだよくわかりません。(あるいはないかもしれません。)

キーワード：TSP、special cases、f-factor、disks、linear programming、
combinatorial geometry

7/2(月): 池上敦子(成蹊大・工・経営情報)
「モデル構築について ―ナース・スケジューリング・モデルを中心に―」

　私の研究に対する大きな興味は，対象とする問題の構造を的確にとらえ，解決する
方法を考え出すところにあります．つまりORのおもしろさである「モデル化」と「ア
ルゴリズム構築」です．問題の本質（本当の目的はなんであるのか，本当の制約はな
んであるのか）を見定めることにより，そのアプローチ方法を検討していく過程は，
とても魅力的です．
　また，現実の問題を突き詰めて分析し，漠然としていた構造が明かになっていくに
つれ，過去の（1950年代からの）ORの基本的モデルや，それを扱うアルゴリズムの重
要さを実感できることに魅力を感じています．
　この発表では，自分がこれまでに出会った問題や楽しかった議論等を織り交ぜなが
ら，現在の主たる研究である「ナース・スケジューリング」の深みに，はまり込んで
いった過程を紹介させて頂けたらと思っております．

7/9(月): 萩田真理子(慶応大・環境情報)
「暗号AESについて」

    　これまで広く使われてきたDESに代わる新しい暗号の標準として、
    J.Daeman, V.Rijmen (2000) により効率よく暗号化、複合化を行う
    ことができて、信頼性の高いAESが開発された。
    　AESには128,192,256ビットのいずれかの鍵を用いることができる。
    鍵サイズは大きいほどセキュリティーを高められるが、計算量も増
    えてしまう。
    　ここではAESの仕組みを説明し、できるだけセキュリティーを下げ
    ずにその計算量を減らすにはどんな方針が考えられるか紹介する。

7/16(月): 岡本吉央(東大・総合文化・広域システム)
「組合せ最適化ゲームのコア」

組合せ最適化ゲームは組合せ最適化問題をもとにした協力ゲームです．それが
もとにする組合せ最適化問題に応じて，最大マッチングゲーム，最小彩色ゲー
ムなどの名前が付けられています．その研究のはじまりはShapley-Shubikによ
る割当ゲーム(二部グラフ上の最大重みマッチングゲーム)にあり，それ以後様々
な組合せ最適化ゲームが提案され，その性質が調べられています．

特に，協力ゲーム理論において重要な概念であるコアに関する研究は熱心にさ
れています．その理由はコアがゲーム理論において重要な概念であるからだけ
ではなく，組合せ最適化問題のコアの非空性がそのもとになっている組合せ最
適化問題の双対性や効率良いアルゴリズムの存在に関わっているからです．し
かし，その関係性は完全に解明されているわけではなく，また，そのような側
面に自覚的な研究はあまりあるとは言えません．

本発表では，コアの非空性ともとの組合せ最適化問題のよい構造に関係がある，
という信念のもとで，いままでに提案された組合せ最適化ゲームを再検討しま
す．そのような視点に立つと，組合せ最適化ゲームという分野は，その基礎と
して，ゲーム理論，グラフ理論，最適化理論，アルゴリズム理論を従え，また，
応用をも視野に入れた非常に魅力的な分野でありながら，なおかつ，未踏の部
分が数多くある魅力的な分野であることがわかってきます．

具体的に扱う内容としては以下のような内容を考えています．

＜前半＞
講演者が最近興味を持っている巡回セールスマンゲームに関して，講演者によ
る結果を紹介します．一般の巡回セールスマン問題は解くことが難しいとされ
ていますが，ある条件を満たす場合は容易に解くことができます．そのような
条件と巡回セールスマンゲームのコアの関係を調べます．

＜後半＞
今まで提案されている組合せ最適化ゲームの中でいくつか興味深いものを紹介
して行きます．具体的には最も古典的な組合せ最適化ゲームである割当ゲーム
と割当ゲームの一般化と見ることもできる最大マッチングゲームを取り上げま
す．もし時間があれば，最小彩色ゲームについても言及します．