Computer Science – Data Structures and Algorithms
Scientific paper
2010-06-23
Computer Science
Data Structures and Algorithms
14 pages. Version 1 of arXiv:0911.2214 includes a preliminary version of this work; version 2 does not
Scientific paper
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 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})) (Alon, Lokshtanov and Saurabh 2009). For betweenness tournament we give an algorithm with runtime O*(2^O(sqrt{OPT/n})), where n is the number of vertices and OPT is the optimal cost. This improves on the previously known O*(OPT^O(OPT^{1/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!
Karpinski Marek
Schudy Warren
No associations
LandOfFree
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-276755