Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set.

If each edge is associated with a weight $w$, the minimum cost feedback arc set problem is to find a $F$ such that $W(F)$ is minimum.

It is well-known that minimum feedback arc set problem is NP-hard, and so does minimum cost feedback arc set problem. I wonder if anyone knows any approximate algorithm that performs well, and any properties of the weight function that can yield a fast solver.

share|improve this question
2  
I guess you are aware of Even, Naor, Schieber, Sudan (1998): "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs" – dx.doi.org/10.1007/PL00009191 ? –  Jukka Suomela Aug 23 '10 at 19:31
    
There were several independent discoveries of polylogarithmic approximations for general feedback arc set. Depending on what precisely you're looking for you may wish to look at all of them. See the papers Leighton and Rao 1999; Seymour 1995; Even et al. 2000; Even et al. 1998 cited in my cs.brown.edu/~ws/papers/fast_journal.pdf . –  Warren Schudy Sep 29 '10 at 21:38

2 Answers 2

  1. Daniel Apon linked to the conference version of my paper. I suggest the draft journal version instead: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .

  2. On tournament graphs some experimental work suggests that local search does quite well. See Anke van Zuylen and Frans Schalekampf's recent ALENEX paper: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .

  3. If the weights satisfy either "probability constraints" or "triangle inequalities" there's a constant-factor approximation algorithm based on quicksort. See Ailon, Charikar and Newman's recent JACM paper.

  4. Can you tell us a bit more about what sorts of instances you have in mind and whether you're looking for something that works well in practice or in theory?

share|improve this answer
    
Your link to Zuylen and Schalekampf is 404 now; informatik.uni-trier.de/~ley/pers/hd/s/Schalekamp:Frans –  nodakai Jul 6 at 16:58

See the paper "How to Rank with Few Errors: A PTAS for Weighted Feedback Arc Set on Tournaments" by Claire Kenyon-Mathieu and Warren Schudy (STOC 2007, journal version on Schudy's page), which gives a Polynomial-time approximation scheme for the special case where the directed graph is a tournament.

share|improve this answer
    
Both papers are very interesting. Besides these, is there any submodular function based approach around? –  miao Aug 24 '10 at 21:44
1  
Please give links. –  Emil Aug 29 '10 at 15:50
    
@Emil, copy/pasting the name of the paper into Google gives you a PDF on the first hit: PDF. –  Daniel Apon Sep 11 '10 at 20:56
    
I was merely suggesting a way of improving the answer. –  Emil Sep 11 '10 at 21:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.