Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
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 Θ(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. © 1998 Elsevier Science B.V. All rights reserved.
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
Dorit S. Hochbaum, Nimrod Megiddo, et al.
Mathematical Programming
Andrew Skumanich
SPIE Optics Quebec 1993
Jianke Yang, Robin Walters, et al.
ICML 2023