マトロイド的特性に関する点除去問題のプライマル・デュアル法による近似
スポンサーリンク
概要
- 論文の詳細を見る
本稿は、グラフの遺伝的特性に関する点除去問題に対する多項式時間近似可能性について論じる。そのような点除去問題は一般にNP-困難であるが、極小禁止グラフが有限個しか存在しない特性の場合、最小値の高々ある定数倍の値をもつ近似解が効率良く求められることが知られている.これに対し、極小禁止郭グラフが無限個存在する場合は、帰還点集合問題を唯一の例外として、そのような多項式時間アルゴリズムは知られていない.ここでは、どのようなグラフの辺集合の上でも定義できるようなマトロイドによって導入される遺伝的特性に着目する。まず初めに、そのような特性に関する点除去問題全てが一様に、簡単かつ新しい整数計画として定式化されることを示す。そして、この整数計画ならびにその線形計画緩和の双対から、そのよつな点除去問題全てに対するプライマル・デュアル近似アルゴリズムを設計する.このアルゴリズムを解析し、保証できる近似比の一般式を与える。次に、このブライマル・デュアル近似アプローチの応用の一つとして、帰還点集合問題が唯一の例外ではないことを示す.即ち,極小禁止グラフを無限個もちながら、対応する点除去問題において近似比2の解力勤率良く計算できるような遺伝的が他にも、しかも無限掴存在することを示す。グラフのマトロイダル・ファミリーという概念とその定義の緩和から、そのようなグラフ特性を導く.しかも、そのような特性の無限列は、点被覆問題や帰還点集合問題におけるグラフ特性の一般化となっている。
- 一般社団法人情報処理学会の論文
- 1997-01-23
著者
関連論文
- 3-連結グラフに対する点被覆及び連結点被覆問題について
- 枝重み付きカクタスに対する発火系列問題の解法
- 劣モジュラ被覆問題の近似について
- いくつかのハイパーグラフ問題に対するPrimal-Dual近似アルゴリズムについて
- マトロイド的特性に関する点除去問題のプライマル・デュアル法による近似