¿Algún algoritmo rápido para un problema de conjunto de arco de retroalimentación de costo mínimo?

En un gráfico dirigido, , F ⊂ E , si G ∖ F es un DAG (gráfico acíclico dirigido), F se llama un conjunto de arco de retroalimentación. $G=(V,E)$$F\subset E$$G\setminus F$$F$

Si cada borde está asociado con un peso , el problema del conjunto de arco de retroalimentación de costo mínimo es encontrar una F tal que W ( F ) sea ​​mínimo.$w$$F$$W(F)$

Es bien sabido que el problema del conjunto de arco de retroalimentación mínima es NP-hard, y también lo hace el problema del conjunto de arco de retroalimentación de costo mínimo. Me pregunto si alguien conoce algún algoritmo aproximado que funcione bien, y cualquier propiedad de la función de peso que pueda producir un solucionador rápido.

1. Daniel Apon vinculado a la versión de la conferencia de mi artículo. Sugiero el borrador de la versión de la revista en su lugar: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .

2. En los gráficos de torneos, algunos trabajos experimentales sugieren que la búsqueda local funciona bastante bien. Ver el reciente artículo ALENEX de Anke van Zuylen y Frans Schalekampf: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .

3. Si los pesos satisfacen las "restricciones de probabilidad" o las "desigualdades de triángulos", existe un algoritmo de aproximación de factor constante basado en la clasificación rápida. Ver el reciente artículo de JACM de Ailon, Charikar y Newman.

4. ¿Puede contarnos un poco más sobre qué tipo de instancias tiene en mente y si está buscando algo que funcione bien en la práctica o en teoría?

Vea el documento "Cómo clasificar con pocos errores: un PTAS para el arco de retroalimentación ponderada establecido en torneos" por Claire Kenyon-Mathieu y Warren Schudy (STOC 2007, versión de revista en la página de Schudy), que ofrece un esquema de aproximación de tiempo polinómico para el caso especial donde el gráfico dirigido es un torneo.