アイテムの入れ替えを許すオンラインナップザック問題について

スポンサーリンク

概要

論文の詳細を見る
本稿では、岩間・武富によって導入された除去可能オンラインナップザック問題のk複数解モデルの制限を緩和した入れ替え可能k複数解モデルを考案する。除去可能k複数解モデルは、通常では認められていない1度ナップザックに入れたアイテムを捨てる事を許可している。さらにk個のナップザックを持ちその中で最もコストが大きいナップザックを出力とする問題である。k≧2の場合には、競合比の上下限が1,3815である事が示されている。このモデルでは、1度ナップザックに入れたアイテムは他のナップザックに移す事が認められていなかった。そこで本稿ではこれを認めたモデルを入れ替え可能k複数解モデルとして定義し考察した。主要結果としてk=2の場合の競合比の上限が1.3333、下限が1.2808である事を示す。また、入れ替えが許されないモデルでは、k≧2の場合に競合比が変化しないが、入れ替えを許すと、kと共に競合比はいくらでも改善出来ることを示す。
社団法人電子情報通信学会の論文
2003-04-18

著者

関連論文

もっと見る

スポンサーリンク