RA-008 A Deterministic Approximation Algorithm for Maximum 2-Path Packing

スポンサーリンク

概要

• 論文の詳細を見る

• 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-ε≈0.5223-ε for any constant ε>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-ε for any constant ε>0).

• 2009-08-20

著者

• Chen Zhi-zhong

  電機大

• 店橋 路可

  電機大

関連論文

• RA-008 A Deterministic Approximation Algorithm for Maximum 2-Path Packing

スポンサーリンク