今日はちょっと低調．
ほとんど何もしてないのに等しい．
昨日、publishされないと書いたものについて、少なくとも投稿だけはしようという気になって来た。
だいぶ迷っていたのだけれども、各方面の方々から御意見をいただき、そうすることにしました。
でも、投稿するのは4月以降になると思います。
(というのは、今は身分が宙ぶらりんだから。)
集めた論文のうち、ある論文ではマッチング複体がマトロイドインターセクション(2つのマトロイドのインターセクション)として書ける場合の特徴付けを与えている。
これはなかなか面白い。
というか、僕の最近の書き物ではマッチング複体がマトロイドとして書ける場合の特徴付けを与えたのだけれども、証明はとても簡単だった。(言明が自明かどうかは別問題だと思われる。)
で、それがあまりにも簡単だったので、その書き物はpublishされないと思うけども、
こちらのマトロイドインターセクションの方は結果も綺麗だし、証明も簡単ではない。
ということで、なかなか価値がありそう。
と書いてしまって、あれ、証明は簡単でないほうがよいのだろうか、と思ってしまった。
証明は簡単なほうがよいと思うのだけれども、証明の難しさ自体がその定理の非自明さを表しているのだとすると、全体的な評価(つまり、定理とその証明を含んだ論文自体のよさ)というのはどうやって見ればよいんだろうか。
で，凸多面体の最小三角形分割のことが某所で話題になっていたので，簡単に述べますと，
僕がはじめてこれを聞いたのはISMP2000だったんですが，このときはDe Loeraさんが話してました．
証明は全然わからなかったです．
SATを使っている，ということぐらいしかわからなかったです．
で，その後，去年の秋の三角形分割のワークショップでRichter-Gebertさんがこれについて講義してくれましたが，やはりわからなかったです．
で，最近の話ですが，ISSAC2001で，最小三角形分割の近似アルゴリズムのはなしが出ていたような気がしたので，チェックし直してみるとやはりありました．
で，この論文によれば，SODA2001ですでに近似比2のアルゴリズムが提案されていて，ISSAC2001の論文は特殊ケースに対する近似比の改良，という話のようです．
(SODAもチェックしていたつもりだったんですが，甘かったです．)
うぅん，研究って知らない間にどんどんと進んで行ってしまうんですね．
ということで，取り敢えずは，単純多面体の中でも比較的単純な構造をしている超立方体の向き付けについてサーベイ．
例としては，線形計画問題の単体法の探索として，そういう向き付けがでてくる．
あと，面白いのは，線形相補性問題もそのような向き付けに関わっている，ということ．
この場合には向き付けは向き付けでもちょっと変な向き付けになるようだ．
最近の興味は，Geometric OptimizationのWell solvable problemについて．
例えば，Combinatorial Optimizationだと，効率良く解ける場合というのはだいたい多面体的組合せ論を通して理解され，また，そうされるべきだ，というのが一つのパラダイムになっている．
けども，どうやら，一見したところでは，Geometric Optimizationは違うようなのだ．
そもそも多項式時間で解けるぐらいでは効率がよい，とは言わないみたいで，「効率がよい」っていうのの尺度そのものが違っているような気もする．
また，Combinatorial Optimizationに対する「多面体的組合せ論」のような役割をするものが見受けられない．
もう少し突っ込んで言うと，統一的なアプローチがないように見える．
もっとも，幾つかの基本的な技法っていうのはあって，それらを用いていろんな問題が効率よく解けてしまうのだけれども，
それらの技法というのが何か問題の背後にある構造を捉えているのかどうなのか，というのがよくわからない．
例えば，LP-type problemっていうものもある種のそういう技法なのだけれども，いろんな問題をそれに帰着させるのはそれ程自明ではない．
そもそも，LP自体がLP-type problemである，ということも自明ではない．(つまり，少し工夫がいる．)
もう一つ気になっている点がある．
「多面体的組合せ論」を基調とするCombinatorial Optimizationの理論は，その核に「線形計画法の双対定理」を持っている．
しかし，Geometric Optimizationの議論では双対性がどのように顔を出して来るのか不明である．
もちろん，「双対変換」という強力な手法はあるが，それは「線形計画法の双対定理」というものとは違うものだ．
面白い点は，非凸最適化で書き表されるようなGeometric Optimizationの問題に効率良く解けるものがある，ということだ．
その問題は結局LP-type Problemになる，ということでその解法を用いて効率良く解けてしまうのだが，LP-type Problemに線形計画法(あるいは，凸計画)にあるような双対定理はなさそうだ，というのが僕の感触である．
なぜかというと，LP-type Problemはgreedoidを含んでいて，そして，Dietrichによると，greedoidに対する双対定理は作れないだろう，ということだから．
ということは，何が結局Geometric Optimizationの理論を支配すべきなのか，というところに向かうと，てんで見当がつかない．
その支配法則は何なのだろうか，というのが最近の(ここ数日の)興味です．
で，上の段落で「Geometric Optimization」とわざわざ英語のまま書いたのは，日本語訳がわからなかったからです．
「幾何最適化」というのを思いつきましたが，そんなことばはいままで聞いたことがないので，書くのをはばかられました．
「Combinatorial Optimization」は「組合せ最適化」という定訳があるのですが，「Geometric Optimization」はどのように訳せばよいのでしょうか．
ということで、テスト勉強をスタートさせなければならない。
授業でPCP定理。
全然わからない。これは要復習だ。
というか、全般的にここらへんの計算量クラスの辺のはなしは初心者には割りと難しい。
つまり、はじめはとっつきにくい、ということ。
これはしっかり考えて見につけることができれば何でもないことなんだけども。
ところで、PCP(Probabilistically Checkable Proof)に対応する日本語は「確率的検査可能証明」ということらしいです。
渡辺先生のページにそう書いてありました。
PとNPについては岩田茂樹先生の「NP完全問題入門」が日本語では圧倒的に支持されているし、僕もよい本だと思う。
しかし、これ以上のもう少し進んだ内容のものだといいものがあるかどうかわからない。
Sipserの本の日本語訳も出たが、原著も日本語訳も読んでいないのでその良さがわからない。
他に、ちょっと進んだ内容の計算複雑性(Computational Complexity)に関する良い本をご存知の方がいらっしゃったら、是非教えて頂きたいです。
(別に、今その本が必要である、というわけではなくて、そういう情報が欲しい、というだけです。情報は命綱なので。)
ところで、僕の出身学科の修論の発表会が終わったようです。
みなさまご苦労さまでした。
と思うと同時に、自分も1年前にそういうことをしたわけなのか、と。
ひっくりかえしていうと、もう1年経ってしまった、ということです。
この1年はほとんど研究をしなかった(とかいうと各方面からいろんな意味で怒られそうですが)、
というよりは、あまりよい研究ができなかった、という感じがします。
論文みたいなものは3つぐらい書きましたが、そのうちの2つはあまり気に入っていなくて、
ジャーナルに採録されるかどうかもわかりません。
なんか、自明なことをやっているような気がしてしまうんですね。
そして、残りの一つは、結果は気に入っているんですが証明がぐちゃぐちゃしているので、その点が難点です。
ということで、研究の出来はわりと満足していないので、来年度にしっかり頑張りましょう、ということにします。
まぁ、それ以上に授業とか演習問題とかたくさんやって(そんなにたくさんでもないかもしれない)、
そういうところで基礎的な考え方とかが身に付いた(と思いこんでいる)ので、
それがプラスになると思う。
ちょっとストレスを感じることがあって、それについて書こうとしたけど辞めた。
(というか、溜っていたストレスが爆発しそうになった。)
要するに、今日もストレスを感じることがあった、ということだ。
(ストレス、というか、憤り、というか、ばかばかしさ、というか、そういうような感じ。)
で、授業が今週で終了するので、来週がテスト。
だから、テスト勉強もしないといけない時期なのですね。
あと、以前書いて投稿中の論文に書いてあることについて、それをもう少しrefineした言明も証明できたような気がする。
ちゃんと書き下してみよう。
[ミニ情報]
Bertsimas-VempalaがSTOC2002で「ランダムウォークで凸計画問題を解く」という論文を発表するようです。
現在、Vempalaのページからプレプリントをとってこれますが、この論文は非常に重要な論文である気がします。
というのは、separation oracleを使って最適化問題をとく枠組として、楕円体法を凌駕しているからです。
ここで、凌駕、というのは、計算量の意味と、アルゴリズムの単純さ、という意味の少なくとも2点があります。
また、ランダムウォークの最適化問題への応用、という意味でも面白い結果です。
で、授業が終わったらまたプロジェクトなので、どういうことをやろうかと考えている。
ということで、いきなりサーベイとか書き出した。