400件目記念インタビュー

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」は,どのような内容ですか?

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

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

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

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

前半では,支配関係と多項式時間で解き得る特殊ケースの関係について記述しました。後半は,これまでの支配関係は項の間でのみ論じられてきましたが,ナップサックの容量制限を介したものを考えてみてはどうかと思い,3つ程,簡単な例を挙げてみました。前半については、かなりの部分が,ビジネス創造センタから出ている 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] は,わずか4ページですが,大変面白い論文です。どちらも,大学生にとってはそれほど難しくはないと思うので,原典にあたってみるとよいと思います。どちらも,商大の図書館で手に入ります。


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

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


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

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

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

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


組合せ最適化全般では
久保幹雄,松井知己: シリーズ【現代人の数理】14『組合せ最適化 [短編集]』朝倉書店,1999
久保幹雄: インターネット時代の数学シリーズ 8『組合せ最適化とアルゴリズム』共立出版,2000
が,私の手元にある中では,比較的平易に読める本だと思います。

かなり専門的になりますが,通読するというよりも,調べものをするときなどに
杉原厚吉,茨木俊秀,浅野孝夫,山下雅史 (編著): 『アルゴリズム工学ー計算困難問題への挑戦』共立出版,2001年
が有用です。

また,組合せ最適化の本としては
Bernhard Korte, Jens Vygen: Combinatorial optimization : theory and algorithms (Algorithms and Combinatorics 21), Springer-Verlag, 4th edition, 2008.
は外せないところです。初版を出して終わりの専門書が多い中,この本は第4版を重ねています。そうそう,以前,ウイングベイ小樽にある喜久屋書店で,訳本を見かけました。とはいえ,専門的知識なしでいきなり読み始めるのは無謀でしょう。図書館にあるのは3rd ed. で,一つ前の版です。

近似アルゴリズムの入門書というのは,不勉強のため知りません。すみません。手元にある中でお勧めは
Vijay V. Vazirani: Approximation Algorithms. Springer-Verlag, corrected 2nd printing, 2003.
ですが,入門としては敷居がやや高いかと思います。こちらも,訳本が,たしかあったと思います。
青字は本学図書館で所蔵しています。リンクをクリックしてご確認ください。
※この推薦本は、2009年9月3日に追記しました(2009年9月24日追加修正しました)。

---

飯田先生、長時間にわたり丁寧に解説いただき、大変ありがとうございました。
また、Barrelについてお気づきの点がありましたらいつでもお知らせください。

なお、『容疑者Xの献身』『Operations Research Letters』は商大図書館にあります。



先生方のご協力のおかげで正式公開から1ヶ月あまりで400件に達しました。ありがとうございました。400編は先生方の御著作のほんの一部でしかありませんので,これからも先生方の研究成果の公開につとめていきたいと思っております。今後とも,ご著作をより多くの人々へ届けるため,論文等をBarrelへ寄贈いただきたくよろしくお願いいたします。