# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 7.4.2016 at 12:20 in S6, there is the following noon lecture:

# Improved Approximation Algorithm for Minimum Feedback Vertex Sets in Tournaments

## Matthias Mnich

## Abstract

(joint work with László Végh and Virginia Vassilevska Williams)

We consider the minimum feedback vertex set problem in tournaments, which finds applications in ranking scenarios. This problem is NP-hard to solve exactly, and Unique Games-hard to approximate by a factor better than two. We present the first 7/3-approximation algorithm for this problem; this improves on the previously best known ratio 5/2, given by Cai et al. in FOCS 1998 / SICOMP 2001.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page