WEKO3
アイテム
A short note on the reducibility of the collapsing knapsack problem
http://hdl.handle.net/10252/1055
http://hdl.handle.net/10252/1055b8a3edff-65e4-4a48-915e-aefbbf5a8e0b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
JOR45(3)_293-298.pdf (286.7 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2008-08-26 | |||||
| タイトル | ||||||
| タイトル | A short note on the reducibility of the collapsing knapsack problem | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 著者 |
Iida, Hiroshi
× Iida, Hiroshi× Uno, Takeaki |
|||||
| 書誌情報 |
Journal of the Operations Research Society of Japan 巻 45, 号 3, p. 293-298, 発行日 2002-09 |
|||||
| 出版者 | ||||||
| 出版者 | Operations Research Society of Japan | |||||
| ISSN / EISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 0453-4514 | |||||
| DOI | ||||||
| 関連タイプ | isIdenticalTo | |||||
| 識別子タイプ | DOI | |||||
| 関連識別子 | 10.15807/jorsj.45.293 | |||||
| 書誌ID（NCID） | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AA00703935 | |||||
| テキストバージョン | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
| 日本十進分類法 | ||||||
| 主題Scheme | NDC | |||||
| 主題 | 410.8 | |||||
| NIIサブジェクト | ||||||
| 主題Scheme | Other | |||||
| 主題 | 数学 | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | 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. In this 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. | |||||
