A short note on the reducibility of the collapsing knapsack problem
スポンサーリンク
概要
- 論文の詳細を見る
This paper deals with the collapsing knapsack problem. In the literature, to solve the problem,a method incorporating a reduction from the problem to the 0-1 knapsack problem has been proposed. Inthis paper we show an alternative reduction which produces coefficients smaller than those by the previous.The improvement makes it possible to solve the resulting 0-1 knapsack problem faster than the previous.On our estimation in a case, the efficiency attains up to 150 times. We also show that the coefficients produced will be the smallest possible.
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
Iida H
Otaru Univ. Hokkaido Jpn
-
Iida Hiroshi
Otaru University of Commerce
-
Uno Takeaki
National Institute of Informatics
-
Uno Takeaki
National Inst. Of Informatics
-
Iida H
Tosoh Corp. Kanagawa Jpn
関連論文
- 頂点被覆に適用されたリスト減少法の解析についての再考
- 整数ナップサックの周期性について : 補遺の補遺
- 無制限整数ナップサック問題をめぐる話題
- 多選択ナップサック問題への新たな緩和問題に向けて
- Maximin型の目的函数を持つナップサック問題に関する考察(神田孝夫名誉教授記念号)
- A Survey of Reductions among Knapsack Problems
- Maximin 型の目的函数を持つナップサック問題について
- 整数ナップサック問題に関するノート(戸島熈名誉教授記念号)
- 多選択ナップサック問題への別緩和
- How to Solve the Collapsing Subset-Sum Problem
- A simple branch-and-bound approach for the strongly correlated knapsack problem
- A short note on the reducibility of the collapsing knapsack problem
- Practical Techniques for Speeding Up Enumeration Algorithms for Frequent Itemset Mining Problems
- A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
- AN O(n^2 log^2 n) ALGORITHM FOR INPUT-OR-OUTPUT TEST IN DISJUNCTIVE SCHEDULING
- Generating Chordal Graphs Included in Given Graphs
- The complexity of free flood filling games (コンピュテーション)
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
- 各項の個数に上限のある整数ナップサックについて (小樽商科大学創立100周年記念号)