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

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

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...

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...