A simple 7/3-approximation algorithm for feedback vertex set in tournaments

Speaker: Samuel Fiorini (Université Libre de Bruxelles)

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 problem in tournaments (FVST). This matches the best deterministic approximation algorithm for FVST due to Mnich, Williams, and Végh (2016), and is a significant simplification and runtime improvement of their approach.

This is a joint work with Manuel Aprile, Tony Huynh and Matthew Drescher.

Date and time: 01/10/2020 at 14:30 (UTC+2)

Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p