Feedback Arc Set Problem in Bipartite Tournaments

摘要

In this paper we give ratio 4 deterministic and randomized approximation algorithms for FEEDBACK Arc Set problem in bipartite tournaments. We also generalize these results to give a factor 4 deterministic approximation algorithm for FEEDBACK Arc Set problem in multipartite tournaments.