|
|
| |
| Universität Bonn -> Institut für Informatik -> Abteilung V | ||
| CS-Reports 2011 | Copyright 2011 Universität Bonn, Institut für Informatik, 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
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |