Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
verfasst von : Marek Karpinski, Warren Schudy
Erschienen in: Algorithms and Computation
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 study fixed parameter algorithms for three problems: Kemeny rank aggregation, feedback arc set tournament, and betweenness tournament. For Kemeny rank aggregation we give an algorithm with runtime
$O^*(2^{O(\sqrt{OPT})})$
, where
n
is the number of candidates,
$OPT \le \binom{n}{2}$
is the cost of the optimal ranking, and
O
*
(·) hides polynomial factors. This is a dramatic improvement on the previously best known runtime of
O
*
(2
O
(
OPT
)
). For feedback arc set tournament we give an algorithm with runtime
$O^*(2^{O(\sqrt{OPT})})$
, an improvement on the previously best known
$O^*(OPT^{O(\sqrt{OPT})})$
[4]. For betweenness tournament we give an algorithm with runtime
$O^*(2^{O(\sqrt{OPT/n})})$
, where
n
is the number of vertices and
$OPT \le \binom{n}{3}$
is the optimal cost. This improves on the previously known
$O^*(OPT^{O(OPT^{1/3})})$
[28], especially when
OPT
is small. Unusually we can solve instances with
OPT
as large as
n
(log
n
)
2
in polynomial time!