日記

2003/2/28

2月終了．
なんか疲れる月だった．集中力もなかったし．

という割りに，昨日と今日は割りと集中した．
やるべきことが明確過ぎて，それをやればよいだけだったから．

HoltがDiscrete Math. 263 (2003) に論文を出してるのを発見したので入手してパラパラ見てみる．
こういうのを見ると，まだまだ自分はHirsch予想が分かっていないな，ということが確認できる．
ということで，こういう論文は勉強になってよい．
Klee-Kleinschmidtもまだちゃんと読んでいないし，Kalai (1992, Discrete & Computational Geometry)も入手したところなので，ちょっとサーベイをするとよい時期かもしれない．

2003/2/26

なんかいまだに集中力が上がらない．
もうそろそろしっかり研究を進めていきたいのに．
ただ，ちょっと疲れてるだけなのかもしれない．どうだろう．

2003/2/20

なかなか集中力が上がらない．
こういうのは困ったものである．

2003/2/18

日本語は難しい．

なんか，自分の論文を読めば読むほど誤植が発見されると言うのはどういうことなんだろう．
やはり集中力が足りないときに書いたりしたのだろうか．
こういうのはよくない．

2003/2/17

今日は本読みの方に重みを置いた．
なかなか進まないし，集中力が切れてくるとその部分だけ読み方が杜撰になったりするので，注意が必要だ．
なので，たぶん一度読み終わっても，もう一度読み返すと思います．

2003/2/14

今日も本読みと論文直し．
もっとも今日は論文直しの方に重点を置いた．
そのためページ数が4ページぐらい増えてしまった．
このままだともう3ページぐらい増えるかもしれない．
とにかくReviseは早めに終わらせたい．

ということで，ちょっと本読みは低調だったのだけども，
表紙カバー案を見せていただいて，ちょっとやる気が復活．

2003/2/13

本読みと論文直し．
ほとんど毎日同じ事をしてるかもしれない．

論文直しをするにも，レフェリーの言っていることをどれくらい取りいれるべきなのかがよく分からない．
というか，そもそも本文そのものを大幅に書き換えてしまいたくなって，そうすることで，コメントがついた部分がそのままなくなってしまうような気もする．
ちょっと慎重に進めないといけないかもしれない．

来学期の授業予定．
実は夏学期が3月31日から始まるという日本では考えられない事態になっているのです．
いまのところ，アシスタントをする授業が月曜の朝と木曜の午後．
本当にアシスタントすべきその授業の演習は金曜日の朝．
これだけでも割りと混んでる気がするのだけども，2つ授業を取ろうと考えている．
一つは，分散コンピューティングの授業で，これは英語で行なわれるはずである．
もっとも英語で行なわれなかったら困ってしまうのだけども．
これは水曜日の午前に行なわれる．
で，もう一つは，セキュリティに関する授業で，こちらも英語で行なわれるはずである．
こちらは火曜日の午後が講義で，木曜日の午後が演習なのだけども，
演習は上記のアシスタントと被ってるので出られないことになる．
自分の興味を広げるという意味でもいい感じだし，また自分の研究していることとどのようなつながりがあるか，ということをいろいろ考える機会になると思う．
また，現在の情報科学や情報技術の広がりにおいて，分散環境やセキュリティは大きな関心事なので世間の流れから取り残されないためにも勉強するべきテーマかと思う．

2003/2/12

今日はLectures on Polytopesを読むのに時間を使った．
実に何度も何度も読んでいるので，そのたびに新鮮な気持ちになることはできないのだけども，
それでもまだ原著にあるタイポとかを新たに発見してしまう，というのは割りと注意深く読んでいない証拠である．
実際今回読んでいる場合でも，どれだけ注意深くやってるか不安になってくる．
ということで，まとまったらしかるべき方に御報告します．

2003/2/11

協力ゲーム理論の勉強をするために，Driessen著の"Cooperative games, solutions and applications"を図書館から借りてきて読んでるのだけども，
この本は自分が知りたいことが証明付きで書かれているのがよい．
昨日，仁が唯一に定まることの証明をはじめて読んだのだけども，この証明はなかなか面白かった．
構成的な証明なのだけども，位相空間論のことば(連続性やコンパクト性)などを使ったりしている．
この証明の構成法自体が仁を求めるアルゴリズムになっているのだけども，これは多項式時間アルゴリズムではない．
ということで，いろいろなケースについて多項式時間アルゴリズムが開発されたり，または，NP-hardnessが示されたりしている．
しかし，それほど多くのケースについて調べられているわけではない．
組合せ最適化ゲーム，という自分が興味あるところでいうと，
割当ゲームに関しては多項式時間アルゴリズムがある．
これはSolymosi-Raghavanの結果で，IJGTの1994年の号に出版されている．
アイディアは仁の一意性に使ったアルゴリズムの改良で，
仁の計算に効いて来る提携の数が少ないことがポイントの一つになっている．
また，松井先生が彼らのアルゴリズムの計算量を改善するアイディアを出している．
最小コスト全張木ゲームについてはMegiddoがその特殊ケースに多項式時間アルゴリズムを出している．
1987年のMath of ORに出ている．
これは論文自体がまだ入手できないため(ジャーナルが貸し出されてしまっているため)どういうアルゴリズムだかわからないのだけれども，シンプルであることが予想される．
一般の最小コスト全張木ゲームについてはFaigle-Kern-KuipersがNP-hardnessを示している．
これは1998年のIJGTである．
仁の計算に関するhardness resultはこれがはじめてのような気がする．
また，組合せ最適化ゲームではないけども，凸ゲームに対してはKuipersが多項式時間アルゴリズムを考案している．
これはテクニカルレポートとしては出ているようだけどもジャーナルには出ていない．
凸ゲームに対するアルゴリズムの拡張であると思われるアルゴリズムがFaigle-Kern-Kuipersによって提案されていて，これも多項式時間アルゴリズムである．
このアルゴリズムは2001年のIJGTに出ていて，楕円体法を使っている．
論文の中ではKuipersの凸ゲームに対するアルゴリズムにも言及していて，Kuipersのアルゴリズムが特殊ケースとして得られるようなことが書いてある．
凸ゲームに対するアルゴリズムで劣モジュラ関数最小化が使われていることも興味深い．

というところが，これまで調べた限りにおける仁に関するアルゴリズムの研究なので，やるべきことがぽこんぽこん空いている，という気はする．
もっとも協力ゲームに関するアルゴリズム自体がなかなか研究されにくい対象になっているようなのだけども，もっと研究されるべき対象だと考えている．

ということで，OR学会誌の2003年2月号に毛利さんのお手伝いをさせてもらって記事が出ることになっています．
これはあまりアルゴリズムではなくてもっと構造的なはなしになっているのですが，
数理的な綺麗さみたいなのを出してみようと思いました．
読まれた方が興味を持っていただけると幸いです．

もう一言付け加えておくと，
1月号に出た毛利さんの記事は下書きのものが載ってしまったようです．
(実は船便がまだ届いていないので，まだ直に見てしまったわけではないんですが．)
なので，本来載るはずだった「幻の原稿」というのがあるそうです．
(というか，それを岡本は毛利さんから頂いて，持っています．)
協力ゲーム理論と幻の原稿の両方に興味がある方は，岡本まで御連絡いただけるとありがたいです．

2003/2/6

ちょっと息切れ気味．なかなか査読が進まない．
というのは，参照してる本を図書館で借りたいのだけども，現在貸し出し中で参照できないから．
これはちょっと困った問題になっている．
もっとも，別のことで参照したい本もあるのだけども，それは図書館に存在すらしていない．
その本はKluwerの本なので買うことは不可能に近い．
これも困ったことになっている．

そういえば，昨日ようやく投稿した．
なんかどう考えても受理されなそうな気がするんですが，まぁ試しに投稿してるようなもので，受理されれば嬉しいな，というようなところです．

2003/2/5

最近ゲーム理論熱が高まっているので，いろいろ勉強しているのだけども，
どうも仁の計算に関する研究はなかなか大変なことになっている．
そもそも定義が簡単ではないので，計算自体も難しそうだと想像がつくのだけども，
多項式時間で計算できるような特殊ケースでも，そのアルゴリズムがなかなか難解なのである．
例えば，特性関数が凸(つまり，優モジュラとか劣モジュラ)であるときでも，
仁を計算するのに楕円体法を使ってしまう．
これはKuipersによる結果で，後にFaigle, Kern, and Kuipersによって拡張されている．
また，割当ゲームに関しても仁の計算が多項式時間で出来ることがわかっている．
これはSolymosiとRaghavanによる結果なのだけども，
こちらの方は，割当ゲームのコアの性質を存分に使っている．
この論文を今日ようやく入手したので，しっかり眺めることにしよう．

で，なんでこんなことをしているかというと，ISAACに行きたがっているからです．
ネタとしては，あるクラスの協力ゲームに対してvalueを求めるアルゴリズムを作る，っていう話です．
いまのところ，Shapley値とτ値が多項式時間で計算できることが分かったのですが，
アルゴリズム自体が割りと簡単(というか基本的な技法ですぐ出来てしまった)ので，
もう少し頑張りたいな，ということになっているのです．
ということで，次は仁かな，と思ったのですが，やはり仁は敷居が高い．
割当ゲームのようにうまくいくには，もっとコアのことが分かっていないと行けないので，
そこら辺をまず調べることになるのかもしれない．
でも，それがうまくいくと，LP双対性とかいろいろおまけがついてくるので，
研究としては格段に面白くなりそうな気がする．

2003/2/4

なぜかLaTeXを再インストールしたりしたために，時間をたくさん消費してしまった．

今日でプレドクの授業の月曜日火曜日の方が終わりになりました．
内容は，コンピュータグラフィクスの基本である曲線・曲面のモデリングの話でした．
ベジエやBスプラインなどの基本的なところから最新の話題までなかなか楽しかったです．

2003/2/3

なんか最近，更新頻度が落ちてる気がするので，ちょっと気をつけるようにしたいと思います．

このところ授業に出てるので異様に眠い．
普段よりも朝が1時間ぐらい早くなってて，
しかも起きなくてはいけないというプレッシャーが逆に熟睡を妨げている，という変な悪循環を起こしている．
しかし，そのような生活も今週で最後になる見とおし．
つまり，今週で授業期間がおしまいになるのである．
ということで，来週からはもう少し研究に専念できる(はず)．

レフェリーレポートが返って来たので見ようと思ったけど，Word文書だった．
Plain textかPDFで送ってもらいたいものである．
まぁ，個人的にはPostscriptもよいのだけど．
ということで，reviseもがんばらないといけない．

今日来たメールによると順序集合に関する新しい本が出るようです．ここに情報があります．
目次をみたところでは，割りと楽しそうな本ではあります．

1月の日記

[トップ]

okamotoy@uec.ac.jp

Last modified:Tue Mar 4 00:22:24 2003