Research output

A 7/3-Approximation for Feedback Vertex Sets in Tournaments

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Associated researcher

  • Mnich, M.

  • Vassilevska Williams, V.
  • Végh, L. A.

Abstract

We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is NP-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first 7/3 approximation algorithm for this problem, improving on the previously best known ratio 5/2 given by Cai et al. [FOCS 1998, SICOMP 2001].

Documents

  • Full text

    Final published version, 598 KB, PDF-document

View graph of relations

Details

Original languageEnglish
Title of host publication24th Annual European Symposium on Algorithms (ESA 2016)
EditorsPiotr Sankowski, Christos Zaroliagis
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl
Pages67:1-67:14
Number of pages14
Volume57
DOIs
Publication statusPublished - 2016

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl