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

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2011 Copyright 2011 Universität Bonn, Institut für Informatik, Abt. V
89130

17.04.2011

Approximation Schemes for the Betweenness Problem in Tournaments
and Related Ranking Problems (Revised Version)

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

We settle the approximability of the Minimum Betweenness problem in tournaments by designing a polynomial time approximation scheme (PTAS). No constant factor approximation was previously known. We also introduce a more general class of so-called fragile ranking problems and construct PTASs for them. 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:57:22
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope