Similar Search Results

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

Iida, Hiroshi - Department of Economics, Otaru University of Commerce - 2005

整数ナップサック問題は, よく知られた0–1 ナップサック問題の数ある拡張の一つである.0–1 ナップサック問題の拡張ゆえに, 整数ナップサック問題も容易には解けない問題であり,...

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

頂点被覆へのリスト減少法の解析に関する一考察

Iida, Hiroshi - Department of Economics, Otaru University of Commerce - 2007

頂点被覆は, NP 困難な組合せ最適化問題ゆえに, 多項式時間では解き得ないと考えられている. 他方, 頂点被覆にはいくつかの近似解法が提案されている. これら近似解法には, 大きく分けて二種類, 即ち,...

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

Partition のある風景

Iida, Hiroshi - Department of Economics, Otaru University of Commerce - 2008

本稿では, Partition からのreduction によって近似率を導出した事例を三つ, 紹介するとともに, それら事例をもとに, 若干の考察を加える.

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

整数ナップサックの周期性についてあれこれ

Iida, Hiroshi - Department of Economics, Otaru University of Commerce - 2013

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

整数ナップサックの周期性について

Iida, Hiroshi - Department of Economics, Otaru University of Commerce - 2009

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

Discussion paper series no.118 への補遺

Iida, Hiroshi - Department of Economics, Otaru University of Commerce - 2009

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

Comments on knapsack problems with a penalty

Iida, Hiroshi - Department of Economics, Otaru University of Commerce - 2007

The classical binary knapsack problem has numerous generalisations in relation to not only a capacity constraint but also an objective function. In 2006, two knapsack problems have coincidentally been proposed, both of which have an extension of the objective function paying the penalty. This...

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

How to solve the collapsing subset-sum problem revisited

Iida, Hiroshi - Department of Economics, Otaru University of Commerce - 2011

This is a revised version of Iida [5]: We introduce a new type of problem that we shall call collapsing subset-sum problem, and present an algorithm to solve the problem. The problem is a special case of the collapsing knapsack problem, and the algorithm based on a depth-first branch-and-bound...

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

A further addendum to "Some thoughts on the 2-approximation algorithm for knapsack problems: A survey"

Iida, Hiroshi - Department of Economics, Otaru University of Commerce - 2014

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

A Survey of Reductions among Knapsack Problems

Iida, Hiroshi - In: 商学討究 (Shogaku Tokyu) 51 (2000) 1, pp. 145-156

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

1
2
3
4
5
6
7
8
9
10
Next
Last