Richard S. Bird, and Stefan Sadnicki Information Processing Letters Volume 101, Issue 1 , 16 January 2007, Pages 41-45 http://dx.doi.org/10.1016/j.ipl.2006.07.011N人が次々と順番にやって来るので，1列に並んだN個の席に順に座らせることを考える…

Faisal N. Abu-Khzam, and Michael A. Langston Information Processing Letters Volume 101, Issue 1, 16 January 2007, Pages 36-40 http://dx.doi.org/10.1016/j.ipl.2006.08.006ACiD2005論文のジャーナル版． Fellows and Langston (1988) の不思議な論…

Vardges Melkonian Information Processing Letters Volume 101, Issue 1, 16 January 2007, Pages 30-35 http://dx.doi.org/10.1016/j.ipl.2006.07.007動的transshipment problemといえば，Hoppe and Tardos (2000) の結果が有名で，多項式時間で解けること…

Uriel Feige and James R. Lee Information Processing Letters Volume 101, Issue 1, 16 January 2007, Pages 26-29 http://dx.doi.org/10.1016/j.ipl.2006.07.009グラフの最小linear arrangement問題に対する近似アルゴリズム。 Arora, Rao and Vazirani (…

Eric Mc Dermid, Christine Cheng, and Ichiro Suzuki Information Processing Letters Volume 101, Issue 1, 16 January 2007, Pages 13-19 http://dx.doi.org/10.1016/j.ipl.2006.07.005安定結婚問題に関する論文。 Irvingは最近「man-exchange stable mat…

R-Trees: Theory and Applications (Advanced Information and Knowledge Processing)作者: Yannis Manolopoulos,Alexandros Nanopoulos,Apostolos N. Papadopoulos,Yannis Theodoridis出版社/メーカー: Springer発売日: 2005/11/21メディア: ハードカバー …

Houman Alborzi, and Hanan Samet Information Processing Letters Volume 101, Issue 1, 16 January 2007, Pages 6-12 http://dx.doi.org/10.1016/j.ipl.2006.07.010一部ではやっていて、いまや「標準」といってもよいほどの幾何データ構造となったR-木に関…

Andras Recski, and David Szeszler Discrete Applied Mathematics Volume 155, Issue 1, 1 January 2007, Pages 44-52 http://dx.doi.org/10.1016/j.dam.2006.05.0102次元のw×nグリッドの上のシュタイナーネットワーク問題を考える。 しかし、解が存在する…

Jean-Luc Marichal, Ivan Kojadinovic, and Katsushige Fujimoto Discrete Applied Mathematics Volume 155, Issue 1, 1 January 2007, Pages 26-43 http://dx.doi.org/10.1016/j.dam.2006.05.002協力ゲーム理論における「値 (value)」の概念はゲームの集合…

Gregory Gutin, Tommy Jensen, and Anders Yeo Discrete Applied Mathematics Volume 154, Issue 18 , 1 December 2006, Pages 2613-2619 http://dx.doi.org/10.1016/j.dam.2006.02.010Domination analysis (支配解析とでも訳すのだろうか) に関する論文。 G…

先日書いた「演習問題の解答」について，八森さんから「いいこと書いてる」という評をいただいた (2006/11/6のところ)． ありがとうございます． ちなみに八森さんは私が修士まで暮らした研究室の先輩です．

アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編)作者: 岩間一雄出版社/メーカー: 共立出版発売日: 2006/10/10メディア: 単行本購入: 4人 クリック: 118回この商品を含むブログ (31件) を見るこちらも読みました．…

アルゴリズム・サイエンス:入口からの超入門 (アルゴリズム・サイエンスシリーズ 1―超入門編)作者: 浅野哲夫出版社/メーカー: 共立出版発売日: 2006/10/10メディア: 単行本購入: 3人 クリック: 77回この商品を含むブログ (27件) を見るこの本を連日宣伝して…

固定パラメータ容易 (FPT) だと思っていたけど、今考えているアルゴリズムではそれが示せていないことに気付いた。 もう少し改善が必要。

上の「アルゴリズム・サイエンス：入り口からの超入門」でもそうなのですが，演習問題の解答を巻末につけてしまうのはよくないと思っています． 添付解答は自分で考える努力を奪うからです． 演習問題に関して重要なのは，まず自分で考えること，そして考え…

アルゴリズム・サイエンス:入口からの超入門 (アルゴリズム・サイエンスシリーズ 1―超入門編)作者: 浅野哲夫出版社/メーカー: 共立出版発売日: 2006/10/10メディア: 単行本購入: 3人 クリック: 77回この商品を含むブログ (27件) を見る読みました． 以下，書…

投稿した．レベルの高いところに出してるので通ったらかなりうれしい． 一部ではかなり評判のいい内容なんだけど．

秋学校が近づいているので，その準備． 私はオーガナイザーの1人なのかどうかよく分からないけど，いろいろ携わってるのは確かだと思う．

使おうと思ったけどやめた．

F.R. McMorris, Henry Martyn Mulder and Robert C. Powers Discrete Applied Mathematics Volume 154, Issue 18 , 1 December 2006, Pages 2599-2608 http://dx.doi.org/10.1016/j.dam.2006.04.023有限距離空間の中から点をk個とってきてx1,x2,...,xkとした…

数学セミナー 2006年 11月号 [雑誌]出版社/メーカー: 日本評論社発売日: 2006/10/12メディア: 雑誌 クリック: 1回この商品を含むブログ (1件) を見る八森さんが「凸多面体の数学」をお薦めしそこなった記事も掲載．

凸多面体の数学作者: G.M.ツィーグラー,G¨unter M. Ziegler,八森正泰,岡本吉央出版社/メーカー: シュプリンガーフェアラーク東京発売日: 2003/04メディア: 単行本 クリック: 8回この商品を含むブログ (5件) を見るこちらも2万円ぐらいお金が余ってる方にお薦…

離散幾何学講義作者: J.マトウシェク,Jir´i Matousek,岡本吉央出版社/メーカー: シュプリンガーフェアラーク東京発売日: 2005/12メディア: 単行本 クリック: 34回この商品を含むブログ (8件) を見る2万円ぐらいお金が余ってる人にお薦めの本． もちろんそれ…

ダイアログ (対談) を著すためのLaTeXスタイルファイルがあった気がするけど，名前を忘れてしまった． Googleで検索してもうまく出てこない． ご存知の方がいらっしゃいましたら，教えていただけるとありがたいです．

Tassos Dimitriou, Sotiris Nikoletseas and Paul Spirakis Discrete Applied Mathematics Volume 154, Issue 18 , 1 December 2006, Pages 2577-2589 http://dx.doi.org/10.1016/j.dam.2006.04.026グラフ(の頂点集合)上に赤い粒子1個と白い粒子k-1個が置か…

B. De Schuymer, H. De Meyer and B. De Baets Discrete Applied Mathematics Volume 154, Issue 18 , 1 December 2006, Pages 2565-2576 http://dx.doi.org/10.1016/j.dam.2006.04.024自然数nとσに対して，(n,σ) diceというものを次のような仮想的なサイコ…

Nathan Linial and Roy Meshulam Combinatorica Issue Volume 26, Number 4 / August, 2006 Pages 475-487 http://dx.doi.org/s00493-006-0027-9 n-1次元単体のランダム2次元部分複体について考える． モデルは，まず1次元の部分はもとの単体から全て持って…

C. Houdre and T. Stoyanov Combinatorica Issue Volume 26, Number 4 / August, 2006 Pages 455-473 http://dx.doi.org/10.1007/s00493-006-0026-x これまたエクスパンダに関する論文． グラフの直積をとったとき，辺伸張や頂点伸張がどうなるかを評価して…

David J. Grynkiewicz Combinatorica Issue Volume 26, Number 4 / August, 2006 Pages 445-453 http://dx.doi.org/10.1007/s00493-006-0025-yまず，Erdos-Ginzburg-Zivの定理の説明． 位数mの有限アーベル群Gを考えて，Gの要素から成る長さ2m-1の列を考える…

有限数学入門―有限上半平面とラマヌジャングラフ作者: 平松豊一,知念宏司出版社/メーカー: 牧野書店発売日: 2003/08/01メディア: 単行本 クリック: 5回この商品を含むブログ (1件) を見るエクスパンダの本というわけではないけども，エクスパンダの1つである…