We show that performing just one round of the Sherali-Adams hierarchy gives an easy 7/3-approximation algorithm for the Feedback Vertex Set (FVST) problem in tournaments. This matches the best deterministic approximation algorithm for FVST due to Mnich, Williams, and Végh, and is a significant simplification and runtime improvement of their approach.
A simple 7/3-approximation algorithm for feedback vertex set in tournaments / Aprile, M.; Drescher, M.; Fiorini, S.; Huynh, T.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - (2020).
A simple 7/3-approximation algorithm for feedback vertex set in tournaments
Huynh, T.
2020
Abstract
We show that performing just one round of the Sherali-Adams hierarchy gives an easy 7/3-approximation algorithm for the Feedback Vertex Set (FVST) problem in tournaments. This matches the best deterministic approximation algorithm for FVST due to Mnich, Williams, and Végh, and is a significant simplification and runtime improvement of their approach.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
