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

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

MoreLess

Year of publication:	2005-07
Authors:	Iida, Hiroshi
Institutions:	Department of Economics, Otaru University of Commerce
Subject:	組合せ最適化 \| ナップサック問題 \| 貪欲法 \| 多項式アルゴリズム

More details

Extent:	application/pdf
Series:	ビジネス創造センターディスカッション・ペーパー (Discussion papers of the Center for Business Creation).
Type of publication:	Book / Working Paper
Notes:	Published in Discussion paper series (2005), 101: 1-7 7 pages
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010965507