Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2010 Copyright 2010 University of Bonn, Department of Computer Science, Abt. V
89125

24.06.2010

Faster Algorithms for Feedback Arc Set Tournament,
Kemeny Rank Aggregation and Betweenness Tournament

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

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*(2O(\sqrt{OPT})), where n is the number of candidates, OPT ≤ \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*(2O(OPT)). For feedback arc set tournament we give an algorithm with runtime O*(2O(\sqrt{OPT})), an improvement on the previously best known O*(OPTO(\sqrt{OPT})) Alon et al. [2009]. For betweenness tournament we give an algorithm with runtime O*(2O(\sqrt{OPT/n})), where n is the number of vertices and OPT ≤ \binom{n}{3} is the optimal cost. This improves on the previously known O*(OPTO(OPT1/3) Saurabh [2009]), especially when OPT is small. Unusually we can solve instances with OPT as large as n (log n)2 in polynomial time!

Last Change: 11/05/14 at 10:53:33
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V