-
A PTAS for the Subset Sum Reconfiguration Problem
-
Takehiro Ito
,
Erik D.Demaine
整数の集合 A,容量 c のナップサック,整数 k に対し,要素の合計値 (以下,部分集合和という) が k 以上 c 以下になるような A の部分集合 (以下,パッキングという) を見つける問題は,部分集合和問題と呼ばれ,NP 完全であることが知られている.本論文では,与えられた 2 つのパッキング Ao と At の間を段階的に遷移させるシーケンスが存在するかどうか判定する問題を扱う.ここで, …
IPSJ SIG Notes 2011-AL-136(2), 1-8, 2011-08-30
CiNii Link1