Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2009 Copyright 2009 Universität Bonn, Institut für Informatik, Abt. V
85307

06.11.2009

Approximation Schemes for the Betweenness Problem
in Tournaments and Related Ranking Problems

Marek Karpinski and Warren Schudy
[Download PostScript] [Download PDF]

We design the first polynomial time approximation schemes (PTASs) for the Minimum Betweenness problem in tournaments and some related higher arity ranking problems. This settles the approximation status of the Betweenness problem in tournaments along with other ranking problems which were open for some time now. We also show fixed parameter tractability of betweenness in tournaments and improved fixed parameter algorithms for feedback arc set tournament and Kemeny Rank Aggregation. The results depend on a new technique of dealing with fragile ranking constraints and could be of independent interest.

Last Change: 11/05/14 at 10:50:14
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope