WEKO3
アイテム
マトロイド的特性に関する点除去問題のプライマル・デュアル法による近似
https://ipsj.ixsq.nii.ac.jp/records/32248
https://ipsj.ixsq.nii.ac.jp/records/322482d3d9d58-5282-4936-83e6-cd7b40c40e21
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1997 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1997-01-23 | |||||||
タイトル | ||||||||
タイトル | マトロイド的特性に関する点除去問題のプライマル・デュアル法による近似 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | A Primal Dual Approximation of Node - Deletion Problems for Matroidal Properties | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
広島大学工学部第二類(電気系)回路システム工学講座 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Dept. of Electrical Engineering, Hiroshima University | ||||||||
著者名 |
藤戸, 敏弘
× 藤戸, 敏弘
|
|||||||
著者名(英) |
Toshihiro, Fujito
× Toshihiro, Fujito
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 本稿は、グラフの遺伝的特性に関する点除去問題に対する多項式時間近似可能性について論じる。そのような点除去問題は一般にNP?困難であるが、極小禁止グラフが有限個しか存在しない特性の場合、最小値の高々ある定数倍の値をもつ近似解が効率良く求められることが知られている。これに対し、極小禁止グラフが無限個存在する場合は、帰還点集合問題を唯一の例外として、そのような多項式時間アルゴリズムは知られていない。ここでは、どのようなグラフの辺集合の上でも定義できるようなマトロイドによって導入される遺伝的特性に着目する。まず初めに、そのような特性に関する点除去問題全てが一様に、簡単かつ新しい整数計画として定式化されることを示す。そして、この整数計画ならびにその線形計画緩和の双対から、そのような点除去問題全てに対するプライマル・デュアル近似アルゴリズムを設計する。このアルゴリズムを解析し、保証できる近似比の一般式を与える。次に、このプライマル・デュアル近似アプローチの応用の一つとして、帰還点集合問題が唯一の例外ではないことを示す。即ち、極小禁止グラフを無限個もちながら、対応する点除去問題において近似比2の解が効率良く計算できるような遺伝的特性が他にも、しかも無限個存在することを示す。グラフのマトロイダル・ファミリーという概念とその定義の緩和から、そのようなグラフ特性を導く。しかも、そのような特性の無限列は、点被覆問題や帰還点集合問題におけるグラフ特性の一般化となっている。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | This paper is concerned with polynomial time approximability of node-deletion problems for hereditary properties. It has been known that when such a property has only a finite number of minimal forbidden graphs the corresponding node-deletion problem can be efficiently approximated to within some constant factor of the optimum. On the other hand when there exist infinitely many minimal forbidden graphs no constant factor approximation has been known except for the case of the Feedback Vertex Set (FVS) problem in undirected graphs. We will focus our attention to such properties that are derived from matroids definable on the edge set of any graph. It will be shown first that all the node-deletion problem for such properties can be uniformly formulated by a simple but non-standard form of the integer programming. The primal-dual approxiamtion algorithm for all such problems is then presented based on this and the dual of its linear programming relaxation. The performance ratios implied by this approach will be analyzed and given in a general form. We will show next, as an application of the primal-dual approach to the node-deletion problems, that the FVS problem is not the sole exceptional case; i.e., there exist other graph (hereditary) properties with an infinite number of minimal forbidden graphs, for which the node-deletion problems are efficiently approximable to within a factor of 2. In fact, we will show, there are infinitely many of them. Such properties are derived from the notion of matroidal families of graphs and relaxing the definitions for them. It will be observed at the same time that an infinite sequence of such properties is constituted with those for both Vertex Cover and FVS problems at its basis and thus providing a proper generalization of them. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1997, 号 8(1996-AL-055), p. 37-44, 発行日 1997-01-23 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |