整数ナップサック問題が多項式時間で解ける特殊な場合を定める条件について

Hiroshi Iida

ビジネス創造センターディスカッション・ペーパー (Discussion papers of the Center for Business Creation) from Otaru University of Commerce

Abstract: 整数ナップサック問題は, よく知られた0–1 ナップサック問題の数ある拡張の一つである.0–1 ナップサック問題の拡張ゆえに, 整数ナップサック問題も容易には解けない問題であり, 分枝限定法・動的計画法等の一般的な枠組みを用いて解かざるを得ない. しかしその一方で, ある特殊な場合には多項式時間で解けるということも知られている. 本稿では, この特殊な場合に焦点を当て, これまでに行われた研究を概観するとともに, いくつかの話題を提供する.

Keywords: 組合せ最適化; ナップサック問題; 貪欲法; 多項式アルゴリズム (search for similar items in EconPapers)
Pages: 7 pages
Date: 2005-07
References: Add references at CitEc
Citations:

Published in Discussion paper series (2005), 101: 1-7

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ota:busdis:10252/913

Access Statistics for this paper

More papers in ビジネス創造センターディスカッション・ペーパー (Discussion papers of the Center for Business Creation) from Otaru University of Commerce Contact information at EDIRC.
Bibliographic data for series maintained by Miura, Chiho ().