Improved Combinatorial Approximation Algorithms for Feedback Arc Set and Rank Aggregation Problems

Abstract

This paper introduces a simple and fast method to combinatorially approximate the feedback arc set problem on weighted tournaments, a well-known classical NP-hard problem. Our results are as follows:

• A combinatorial 3-approximation algorithm for the \textit{minimum feedback arc set} problem with the expected running time of $O(|V|\log |V|)$ on tournaments that satisfy the probability constraints, where $V$ is the set of vertices of the tournament. The previously best-known approximation factor was 4.
• A combinatorial 5/3-approximation algorithm for the \textit{minimum feedback arc set} problem with the expected running time of $O(|V|\log |V|)$ on tournaments that satisfy both the probability and the triangle inequality constraints. The previously best-known approximation factor was 2.

Although these problems currently have a PTAS algorithm which returns a $1+\epsilon$ approximation solution, the running time is doubly exponential with respect to $1/\epsilon$, being merely significant in theory or practice. Moreover, there are LP-based algorithms that solve these problems with better approximation factors than ours, but, in expense of solve an LP with $O(|V|^2)$ variables and $O(|V|^3)$ constraints which requires an excessive expenditure of time, making them inappropriate to use in practice. Therefore, the main superiority of our algorithms is that they dramatically reduce the running time by slightly increasing these approximation factors.
Another considerable point is that, despite its complex analyses, we obtain these results by a very simple algorithm that can be implemented in several lines of code.

We have also shown that the proposed approach can be applied to other problems. Here, we use the method to approximate the rank aggregation problem and show the superiority of the results compared to the current solutions.