Back to Search
Start Over
A [formula omitted]-approximation algorithm for feedback vertex set in tournaments via Sherali–Adams.
- Source :
-
Discrete Applied Mathematics . Oct2023, Vol. 337, p149-160. 12p. - Publication Year :
- 2023
-
Abstract
- We study the feedback vertex set problem in tournaments from the polyhedral point of view, and in particular we show that performing just one round of the Sherali–Adams hierarchy gives a relaxation with integrality gap 7 / 3. This allows us to derive a 7 / 3 -approximation algorithm for the feedback vertex set problem in tournaments that matches the best deterministic approximation guarantee due to Mnich, Williams, and Végh, and is a simplification and runtime improvement of their approach. [ABSTRACT FROM AUTHOR]
- Subjects :
- *TOURNAMENTS
*ALGORITHMS
*APPROXIMATION algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 337
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 164280761
- Full Text :
- https://doi.org/10.1016/j.dam.2023.04.016