Chudak, FA
Goemans, MX
Hochbaum, DS
Williamson, DP
Recently, Becker and Geiger and Bafna, Berman and Fujito gave 2-approximation algorithms for the feedback vertex set problem in undirected graphs. We show how their algorithms can be explained in terms of the primal-dual method for approximation algorithms, which has been used to derive approximation algorithms for network design problems. In the process, we give a new integer programming formulation for the feedback vertex set problem whose integrality gap is at worst a factor of two; the well-known cycle formulation has an integrality gap of Theta(log n), as shown by Even, Naor, Schieber and Zosin. We also give a new 2-approximation algorithm for the problem which is a simplification of the Bafna et al. algorithm. (C) 1998 Elsevier Science B.V. All rights reserved.
Bibliographic reference |
Chudak, FA ; Goemans, MX ; Hochbaum, DS ; Williamson, DP. A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. In: Operations Research Letters, Vol. 22, no. 4-5, p. 111-118 (1998) |
Permanent URL |
http://hdl.handle.net/2078.1/45588 |