部分集合和遷移問題の多項式時間近似スキーム
スポンサーリンク
概要
- 論文の詳細を見る
整数の集合A,容量cのナップサック,整数κに対し,要素の合計値(以下,部分集合和という)がκ以上c以下になるようなAの部分集合(以下,パッキングという)を見つける問題は,部分集合和問題と呼ばれ,NP完全であることが知られている.本論文では,与えられた2つのパッキングA_0とA_tの間を段階的に遷移させるシーケンスが存在するかどうか判定する問題を扱う.ここで,段階的な遷移シーケンスとは,以下の3つの条件を満たすパッキングの列である.(1)遷移シーケンスはA_0に始まりA_tで終わる.(2)遷移シーケンスに現れるどのパッキングも,その1つ前のパッキングに,Aの要素をただ1つ付け加える,または取り除くことで得られる.(ただし,A_0は除く)(3)遷移シーケンスに現れるどのパッキングも,その部分集合和がκ以上c以下である.本論文では,この判定問題が強NP困難であることを示す.また,制約グラフが与えられる場合には,PSPACE完全であることも示す.ここで,制約グラフの各点はAの要素に対応し,各辺は同時にナップサックに入れることができない要素の組を表す.本論文では,最適化問題も扱う.すなわち,遷移シーケンスに現れるパッキングの中で,部分集合和が最小となるものを最大化する問題である.この最大化問題に対し,我々は多項式時間近似スキーム(PTAS)を与える.一方で,制約グラフが与えられる場合には,APX困難であることも示す.
- 2011-08-30
著者
-
伊藤 健洋
東北大学大学院情報科学研究科
-
DEMAINE Erik
MIT Computer Science and Artificial Intelligence Laboratory
-
伊藤 健洋
東北大学情報科学研究科
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- リスト辺彩色の再構成問題
- 木の均一分割問題
- 需要点と供給点があるグラフの分割問題の近似可能性
- グラフの距離辺彩色アルゴリズム
- 需要点と供給点のあるグラフの分割
- 再構成問題の計算複雑さ
- 需要と供給の木の分割
- 木の最小コスト辺彩色のマッチングへの帰着
- A-025 Finding Reconfigurations between List Edge-Colorings of a Graph
- グラフの距離辺彩色アルゴリズム
- 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学生シンポジウム,シンポジウムセッション)
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- グラフ上の拡散競争ゲームの計算複雑さ
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- Finding a Hamiltonian Path in a Cube with Specified Turns is Hard
- トロミノ詰込問題の計算複雑さについて
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)
- Computational Complexity of Piano-Hinged Dissections
- 次数指定した最大正則誘導部分グラフ探索問題(一般)