Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2011 Copyright 2011 University of Bonn, Department of Computer Science, Abt. V
85321

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
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V