Feedback Arc Set in Tournaments (Masters project):

Given a directed, weighted graph, the feedback arc set problem is to find the minimum weight set of edges whose removal results in an acyclic graph. When the input graph is a tournament--a complete directed graph--the problem has been well studied and a solution very close to an optimal solution can be efficiently computed. This project is to study the feedback arc set for special cases of tournaments based on convex combinations of permutations, for which finding an optimal solution is not known to be NP-hard or efficiently computable.


Further questions about the project: alantha.newman "at" epfl.ch

Responsible professor: Ola Svensson

Back to Theory@EPFL.