| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 6A |
| セッション名 |
| グラフ・ネットワーク |
| 講演日 |
| 2009/09/04 |
| 講演場所(会議室等) |
| A会場（9号館1F 911教室） |
| 講演番号 |
| RA-008 |
| タイトル |
| A Deterministic Approximation Algorithm for Maximum 2-Path Packing |
| 著者名 |
| 店橋 路可, Chen Zhi-Zhong, |
| キーワード |
| 2-path packing problem, approximation algorithm, derandomization, pessimistic estimator method |
| 抄録 |
|
This paper deals with the maximum-weight 2-path packing problem (M2PP), which is the problem of computing a set of vertex-disjoint paths of length 2 in a given edge-weighted complete graph so that the total weight of edges in the paths is maximized. Previously, Hassin and Rubinstein gave a randomized cubic-time approximation algorithm for M2PP which achieves an expected ratio of 35/67 - e (approximately, 0.5223 - e) for any constant e > 0. We refine their algorithm and derandomize it to obtain a deterministic cubic-time approximation algorithm for the problem which achieves a better ratio (namely, 0.5265 - e for any constant e > 0). |
| 本文pdf |
| PDF download (187.4KB) |