Barrelの収録文献が平成20年4月17日に400件を超えました！

400件目の文献は，社会情報学科の飯田浩志先生による，
Iida, Hiroshi（2008）Two Topics in Dominance Relations for the Unbounded Knapsack Problem "The Open Applied Mathematics Journal" 2(1), pp16-19
でした。

飯田先生にお話を伺いました。

Q：登録400件目の論文「Two Topics in Dominance Relations for the Unbounded Knapsack Problem」は，どのような内容ですか？

特に新しい事が書いてある訳ではありません。これまでに知られている別々の事柄を，また違った視点からながめて繋いでみた，サーベイ的な論文というか，メモ書きみたいなものです。

ナップサック問題というのは，ナップサックの中にいくつかの物を入れるとき，重量制限の中で価値を最大とするにはどれを選んだらいいか？という問題で，総当たりで組み合わせる以外の解法があるかどうかがまだ分かってない問題です。

専門的に云えば，ナップサック問題はNP困難な問題の一つで，多項式時間では解き得ないと考えられています。おそらく，ほとんどの研究者がそう信じていると思います。僕もそうです。ナップサック問題が簡単には解き得ない事に依拠した暗号もあります。もし，ナップサック問題が多項式時間で解けたら，P=NPが示された事になって，世界がひっくり返ります。多分，今も世界のどこかで，P≠NP を示そうと頑張っている研究者がいると思います。テレビドラマ『ガリレオ』を覚えてらっしゃいますか？ P≠NP は，湯川学先生が登場する，東野圭吾さんの『容疑者Xの献身』の中にも出てきますよ。

ナップサックの中に入れる物を，１つずつではなくていくつでも取っていいというのが，今回の論文で扱った「整数ナップサック問題」（Unbounded Knapsack Problem：UKP）です。このUKPの特徴の1つに「支配関係」（Dominance Relations）があります。価値が小さくて重量が重いもの k と，価値が大きくて重量が軽いもの j があったら，どちらを重量制限があるナップサックに入れますか？ j を入れます。k は必要ない。これが支配関係です。

前半では，支配関係と多項式時間で解き得る特殊ケースの関係について記述しました。後半は，これまでの支配関係は項の間でのみ論じられてきましたが，ナップサックの容量制限を介したものを考えてみてはどうかと思い，３つ程，簡単な例を挙げてみました。前半については、かなりの部分が，ビジネス創造センタから出ている Discussion Paper Series No.101 と重なるので，こちらが参考になるかと思います。


Q：この研究をはじめられたきっかけは何ですか？

大学院生の頃からずっと，ナップサック問題が面白くて，それが基軸にあります。最初はどうしてはじめたのだったかなあ...ずいぶん前のことで忘れちゃいました。

この論文は、参考文献の [10] に触発されて書き上げました。Zukerman et al [10] は，UKP の最小化問題が，ある特殊なケースでは多項式時間で解けることを論じた論文なんです。その特殊ケースを規定する条件が，最大化問題における支配関係と同じものでした。では逆に，最小化問題における支配関係は，最大化問題でどのような役割をするのだろう？と考えました。


Q：現在の研究について教えてください。

最近は，近似アルゴリズムが面白いなあと。近似アルゴリズムは，だいたいの解を知りたいときに使うものです。ずっとナップサック問題のように最適値を求める問題に取り組んできて近似値には興味がなかったんですが，最近面白いと思うようになりました。で，色々と論文を読んでいます。Operations Research Letters　が特に好きで，ここから研究のネタを拾う事が多いです。

困難な問題が，少し見方を変える事で簡単に解けてしまう，ということがたまにありますが，こういったところに強い興味を覚えます。Opsearch 30(2) 97-116 (1993) は，これまで困難とされてきた strongly correlated knapsack problem を，部分和問題の列に変換して，あっという間に解いてしまいました。これまでで，一番感銘を受けた論文です。Opsearch というのは，インドOR学会の雑誌で，入手には苦労しました。普段は，著者から抜き刷りを送って頂いたり，また，その逆もあります。

また，短い論文が好きです。今回の論文で refer した Zukerman et al [10]や，Hu and Lenard [9] は，わずか４ページですが，大変面白い論文です。どちらも，大学生にとってはそれほど難しくはないと思うので，原典にあたってみるとよいと思います。どちらも，商大の図書館で手に入ります。


Q：Barrelに掲載された文献をどのような人に読んでもらいたいですか。

興味のある方なら，どなたにでも。できるだけわかりやすく書いたので，小説のように，読んでもらいたいです。


Q：Barrelについてご意見，感想をお願いします。

Barrelは，名前の標記方法を統一した方が良いと思います。Iida, Hiroshi と Hiroshi, Iida が混在しているのは，変です。（注：修正いたしました（Barrel担当者））

自分が書いた論文が入手しやすく誰にでも読まれるようになるのは，とてもいいことです。
Barrelは，まだ先が長い膨大な作業だと思いますが，頑張ってください。

  興味を持った方へ！...飯田先生からのオススメ入門書