Un algorithme rapide pour un problème de jeu d'arc de rétroaction à coût minimum?

Dans un graphe dirigé, , F ⊂ E , si G ∖ F est un DAG (graphe acyclique dirigé), F est appelé un ensemble d'arc de rétroaction. $G=(V,E)$$F\subset E$$G\setminus F$$F$

Si chaque bord est associé à un poids , le problème de jeu d'arc à rétroaction de coût minimum est de trouver un F tel que W ( F ) soit minimum.$w$$F$$W(F)$

Il est bien connu que le problème de jeu d'arc à rétroaction minimale est NP-difficile, tout comme le problème de jeu d'arc à rétroaction à coût minimum. Je me demande si quelqu'un connaît un algorithme approximatif qui fonctionne bien et des propriétés de la fonction de pondération qui peuvent produire un solveur rapide.

1. Daniel Apon lié à la version conférence de mon article. Je suggère plutôt la version provisoire du journal: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .

2. Sur les graphiques de tournois, certains travaux expérimentaux suggèrent que la recherche locale fonctionne assez bien. Voir le récent document ALENEX d'Anke van Zuylen et Frans Schalekampf: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .

3. Si les poids satisfont aux «contraintes de probabilité» ou aux «inégalités triangulaires», il existe un algorithme d'approximation à facteur constant basé sur le tri rapide. Voir le récent article JACM d'Ailon, Charikar et Newman.

4. Pouvez-vous nous en dire un peu plus sur les types d'instances que vous avez en tête et si vous cherchez quelque chose qui fonctionne bien en pratique ou en théorie?

Voir l'article "Comment classer avec peu d'erreurs: un PTAS pour un ensemble d'arc de rétroaction pondéré sur les tournois" par Claire Kenyon-Mathieu et Warren Schudy (STOC 2007, version de journal sur la page Schudy), qui donne un schéma d'approximation en temps polynomial pour le cas particulier où le graphe orienté est un tournoi.