2011 | OriginalPaper | Buchkapitel
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
verfasst von : Marek Karpinski, Warren Schudy
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We settle the approximability status 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.