Algum algoritmo rápido para um feedback de custo mínimo é um problema definido?

Em um gráfico direcionado, , , se é um DAG (gráfico acíclico direcionado), é chamado de conjunto de arco de feedback. $G=(V,E)$ $F\subset E$ $G\setminus F$ $F$

Se cada aresta estiver associada a um peso , o problema do conjunto de arcos de feedback de custo mínimo é encontrar um tal que seja mínimo. $w$ $F$ $W(F)$

É sabido que o problema do conjunto de arco de feedback mínimo é difícil para NP, assim como o problema do conjunto de arco de feedback de custo mínimo. Gostaria de saber se alguém conhece algum algoritmo aproximado com bom desempenho e quaisquer propriedades da função de peso que possam gerar um solucionador rápido.

ds.data-structures graph-theory np-hardness approximation-algorithms miao
fonte

Eu acho que você está ciente de Even, Naor, Schieber, Sudão (1998): "Aproximando conjuntos mínimos de feedback e multicuts em gráficos direcionados" - dx.doi.org/10.1007/PL00009191 ?

Jukka Suomela 23/08/10

Houve várias descobertas independentes de aproximações polilogarítmicas para o conjunto de arco de feedback geral. Dependendo do que exatamente você está procurando, você pode querer olhar para todos eles. Veja os artigos Leighton e Rao 1999; Seymour 1995; Even et al. 2000; Even et al. 1998 citado em meu cs.brown.edu/~ws/papers/fast_journal.pdf .

Warren Schudy

Só queria esclarecer - é certo que apenas o problema direcionado é difícil para NP e o problema para gráficos não direcionados pode ser resolvido em tempo polinomial, consulte, por exemplo, discussão sobre stackoverflow "Como encontrar a borda de feedback definida no gráfico não direcionado". É correto que o problema possa ser resolvido em tempo polinomial para gráfico não direcionado?

TomR

@TomR Uma aresta de feedback de peso mínimo definida em um gráfico não direcionado possui uma árvore de abrangência de peso máximo como complemento, que você pode encontrar no polytime.

G. Bach

talvez isso ajuda: arxiv.org/pdf/1702.07612.pdf aplausos e boa sorte

user44477

Respostas:

Daniel Apon vinculado à versão da conferência do meu artigo. Sugiro a versão preliminar do periódico: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .
Nos gráficos de torneios, alguns trabalhos experimentais sugerem que a pesquisa local se sai muito bem. Veja o recente artigo ALENEX de Anke van Zuylen e Frans Schalekampf: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .
Se os pesos atendem a "restrições de probabilidade" ou "desigualdades de triângulo", existe um algoritmo de aproximação de fator constante baseado no quicksort. Veja o recente artigo do JACM de Ailon, Charikar e Newman.
Você pode nos contar um pouco mais sobre que tipo de casos você tem em mente e se está procurando algo que funcione bem na prática ou na teoria?

Warren Schudy
fonte

Seu link para Zuylen e Schalekampf agora é 404; informatik.uni-trier.de/~ley/pers/hd/s/Schalekamp:Frans

nodakai

Veja o artigo "Como classificar com poucos erros: um PTAS para arco de feedback ponderado definido em torneios", de Claire Kenyon-Mathieu e Warren Schudy (STOC 2007, versão de revista na página de Schudy), que fornece um esquema de aproximação em tempo polinomial para o torneio. caso especial em que o gráfico direcionado é um torneio.

DS
fonte

Ambos os papéis são muito interessantes. Além desses, existe alguma abordagem baseada em função submodular?

Miao

Por favor, dê links.

Emil

@Emil, copiar / colar o nome do artigo no Google fornece um PDF no primeiro clique: PDF .

Daniel Apon

Eu estava apenas sugerindo uma maneira de melhorar a resposta.

Emil