訳本のページのために、外国人名読み方一覧を作っているけど、
どうも迷うところが多過ぎて困っている。
(そもそも、そのために本の中では無理にカタカナにしなかったわけだから。)
いろいろ調べると、いままでそうだと思い込んでいた読み方が全く違っていることもあり、
また、知らない間に亡くなってる人もいることが分かった。
今日調べたところでは、Szekeresが今年、しかも奥さんと同日に亡くなったようだ。
御冥福をお祈りしたい。
Zieglerのページの写真が新しくなってるのを発見。
僕が2005/10/14に紹介した、
ナッシュ均衡計算のPPAD完全性について、
進展があったようです。
ECCCを見ていたら、プレイヤー数が3のときのPPAD完全性も
証明されたようです。
これで残るは、プレイヤーが2人の場合だけになりました。
n個風船があって、それらを膨らませたい。
i番目の風船の容量は1/iであるが、外見から、風船同士は見分けがつかない。
風船に容量以上の空気を入れてしまうと、その風船は割れてしまう。
このとき、風船にできるかぎりたくさん空気を詰めるにはどうしたらよいだろうか?
ただし、詰められた空気というのは、割れずに残った風船の中に入れられた空気の総量のことである。
これはアルゴリズムの問題であるが、
Ericksonのページには1だけ詰めるdeterministicな方法 (これはすぐに思い付く) と、
deterministicな方法では最悪の場合1より多く詰められないこと (これはadversary argumentから従う) が出ていて、
randomizedな方法では、期待値をおよそ1.7183にできるというMahdianの方法が紹介されている。
Ericksonの学生はこれをもう少しだけ改善できると言っているそうだけど、
一体どこまで改善できるのか、ということはよく分からないそうだ。
なかなか面白いので自分でも考えてみたけど、改善には至らなかった。
もう少し考えてみたい。
(これを、計算限界の会議の未解決問題として出せばよかったかもしれない。勝手に変更してしまおうか…。)
その他、多目的最適化について少々。
コマゼミの準備も大体できた。
今回は板書でやる予定なので、ちょっとワクワクする。
2時間ぐらいで終わらないかもしれないけど。
訳本。
索引の校正も終わった。
出版が段々近付いてきて、ちょっとワクワクする。
担当の編集者の方にとても感謝。