Linear programming based approximation algorithms for feedback set problems in bipartite tournaments |
| |
Authors: | Anke van Zuylen |
| |
Affiliation: | Institute for Theoretical Computer Science, Tsinghua University, Beijing, China |
| |
Abstract: | We consider the feedback vertex set and feedback arc set problems on bipartite tournaments. We improve on recent results by giving a 2-approximation algorithm for the feedback vertex set problem. We show that this result is the best that we can attain when using optimal solutions to a certain linear program as a lower bound on the optimal value. For the feedback arc set problem on bipartite tournaments, we show that a recent 4-approximation algorithm proposed by Gupta (2008) 8] is incorrect. We give an alternative 4-approximation algorithm based on an algorithm for the feedback arc set on (non-bipartite) tournaments given by van Zuylen and Williamson (2009) 14]. |
| |
Keywords: | Feedback vertex set Feedback arc set Bipartite tournament Approximation algorithm Linear programming |
本文献已被 ScienceDirect 等数据库收录! |