Can I read A Simple 7/3-Approximation Algorithm for Feedback Vertex Set in Tournaments on EtoBox?

A Simple 7/3-Approximation Algorithm for Feedback Vertex Set in Tournaments by Aprile, Manuel; Drescher, Matthew; Fiorini, Samuel; Huynh, Tony is a scholarly article available to read on EtoBox.

What is A Simple 7/3-Approximation Algorithm for Feedback Vertex Set in Tournaments about?

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\'egh, and is a significant simplification and runtime improvement of their approach.

Author

Aprile, Manuel; Drescher, Matthew; Fiorini, Samuel; Huynh, Tony

Published

2020

Language

EN