| 講演名 | 2020-03-01 Power Vertex Cover問題の近似アルゴリズムについて 立松 拓己(豊橋技科大), 林谷 哲郎(豊橋技科大), 藤戸 敏弘(豊橋技科大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Vertex Cover を拡張するPower Vertex Cover 問題について，新たに2つの2倍近似アルゴリズムを提案する． Power Vertex Cover では，グラフG = (V,E) に加え，各辺e ∈ E を被覆するために必要な重みとしてw(e) が入力として与えられる． 辺e = {u, v} を被覆するためには，p(u) ? w(e) またはp(v) ? w(e) のいずれかを満たすように， Power p ∈ R^V_+ を各頂点に割り当てる必要がある．Power Vertex Cover は，すべての辺を被覆するために割り当てられたPower の総和を最小化する問題であり，全ての辺e ∈ E についてw(e) = 1 である場合に通常のVertex Cover と一致する．本稿では，同問題に対し，LP 緩和の丸め法および局所比定理に基づき，2種類の2倍近似アルゴリズムを提示する． |
| 抄録(英) | We present two 2-approximation algorithms for Power Vertex Cover problem, which is a generalization ofthe Vertex Cover problem. Given in Power Vertex Cover is a graph G = (V,E) with “edge” weights w(e), and an edge e = {u, v} is covered only if power p ∈ R ^V_+ assigned on the vertices satisfy either p(u) ? w(e) or p(v) ? w(e). We aim to find a power assignment of minimum sum that covers all edges in G. Clearly, Vertex Cover corresponds to Power Vertex Cover when all edge weights are equal to 1. In this paper, we present two 2-approximation algorithms for this problem, one designed based on LP rounding and the other based on the local ratio theorem. |
| キーワード(和) | 頂点被覆問題 / グラフ理論 / 近似アルゴリズム |
| キーワード(英) | Vertex Cover Problem / Graph Theory / Approximation Algorithms |
| 資料番号 | COMP2019-50 |
| 発行日 | 2020-02-23 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2020/3/1(から1日開催) |
| 開催地（和） | 電気通信大学 |
| 開催地（英） | The University of Electro-Communications |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 大舘 陽太(熊本大) / 玉置 卓(兵庫県立大) |
| 幹事氏名（英） | Yota Otachi(Kumamoto Univ) / Suguru Tamaki(Univ. of Hyogo) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Power Vertex Cover問題の近似アルゴリズムについて |
| サブタイトル（和） | |
| タイトル（英） | On Approximation Algorithms for Power Vertex Cover Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 頂点被覆問題 / Vertex Cover Problem |
| キーワード(2)（和/英） | グラフ理論 / Graph Theory |
| キーワード(3)（和/英） | 近似アルゴリズム / Approximation Algorithms |
| 第 1 著者 氏名（和/英） | 立松 拓己 / Takumi Tatematsu |
| 第 1 著者 所属（和/英） | 豊橋技術科学大学(略称：豊橋技科大) Toyohashi University of Technology(略称：TUT) |
| 第 2 著者 氏名（和/英） | 林谷 哲郎 / Tetsuro Rintani |
| 第 2 著者 所属（和/英） | 豊橋技術科学大学(略称：豊橋技科大) Toyohashi University of Technology(略称：TUT) |
| 第 3 著者 氏名（和/英） | 藤戸 敏弘 / Toshihiro Fujito |
| 第 3 著者 所属（和/英） | 豊橋技術科学大学(略称：豊橋技科大) Toyohashi University of Technology(略称：TUT) |
| 発表年月日 | 2020-03-01 |
| 資料番号 | COMP2019-50 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | COMP-433 |
| ページ範囲 | pp.29-33(COMP), |
| ページ数 | 5 |
| 発行日 | 2020-02-23 (COMP) |