部分集合和遷移問題の多項式時間近似スキーム
スポンサーリンク
概要
- 論文の詳細を見る
整数の集合 A,容量 c のナップサック,整数 k に対し,要素の合計値 (以下,部分集合和という) が k 以上 c 以下になるような A の部分集合 (以下,パッキングという) を見つける問題は,部分集合和問題と呼ばれ,NP 完全であることが知られている.本論文では,与えられた 2 つのパッキング Ao と At の間を段階的に遷移させるシーケンスが存在するかどうか判定する問題を扱う.ここで,段階的な遷移シーケンスとは,以下の 3 つの条件を満たすパッキングの列である.(1) 遷移シーケンスは Ao に始まり At で終わる.(2) 遷移シーケンスに現れるどのパッキングも,その 1 つ前のパッキングに,A の要素をただ 1 つ付け加える,または取り除くことで得られる.(ただし,Ao は除く) (3) 遷移シーケンスに現れるどのパッキングも,その部分集合和が k 以上 c 以下である.本論文では,この判定問題が強 NP 困難であることを示す.また,制約グラフが与えられる場合には,PSPACE 完全であることも示す.ここで,制約グラフの各点は A の要素に対応し,各辺は同時にナップサックに入れることができない要素の組を表す.本論文では,最適化問題も扱う.すなわち,遷移シーケンスに現れるパッキングの中で,部分集合和が最小となるものを最大化する問題である.この最大化問題に対し,我々は多項式時間近似スキーム (PTAS) を与える.一方で,制約グラフが与えられる場合には,APX 困難であることも示す.
- 2011-08-30
著者
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- リスト辺彩色の再構成問題
- 木の均一分割問題
- 需要点と供給点があるグラフの分割問題の近似可能性
- グラフの距離辺彩色アルゴリズム
- 需要点と供給点のあるグラフの分割
- 再構成問題の計算複雑さ
- 需要と供給の木の分割
- 木の最小コスト辺彩色のマッチングへの帰着
- グラフの距離辺彩色アルゴリズム
- Reconfiguration of list edge-colorings in a tree (コンピュテーション)
- 需要点と供給点のある木のコスト最小分割
- 部分集合和遷移問題の多項式時間近似スキーム
- 木の最小コスト辺彩色のマッチングへの帰着
- 需要点と供給点のある木のコスト最小分割
- 木のリスト辺彩色の遷移可能性
- 部分集合和遷移問題の多項式時間近似スキーム
- 木,カクタスにおける点被覆の遷移可能性 (コンピュテーション)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 木,カクタスにおける点被覆の遷移可能性
- DS-1-9 グラフのL(2,1)ラベリングの遷移可能性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- グラフ上の拡散競争ゲームの計算複雑さ
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- トロミノ詰込問題の計算複雑さについて
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)
- 次数指定した最大正則誘導部分グラフ探索問題(一般)