Algoritmos gananciosos ideais para problemas difíceis de NP

A ganância, por falta de uma palavra melhor, é boa. Um dos primeiros paradigmas algorítmicos ensinados no curso introdutório de algoritmos é a abordagem gananciosa . A abordagem gananciosa resulta em algoritmos simples e intuitivos para muitos problemas em P. Mais interessante, para alguns problemas difíceis de NP, o algoritmo ganancioso / local óbvio e natural resulta em (provavelmente) fator de aproximação ideal (sob premissas teóricas de complexidade adequadas). Um exemplo clássico é o problema da tampa do conjunto . Um algoritmo ganancioso natural fornece um fator de aproximação O (ln n), que é ótimo, a menos que P = NP.

Cite alguns algoritmos naturais gananciosos / locais para problemas difíceis de NP que são comprovadamente ideais sob suposições teóricas de complexidade adequadas.

O método das expectativas condicionais (para des aleatorizar os algoritmos de "atribuição aleatória" para Max-Cut e Max-SAT) pode ser visto como uma estratégia gananciosa: para , você escolhe o valor de uma variável como que o número esperado de restrições atendidas na instância reduzida resultante excede o número esperado de restrições atendidas na instância atual. (De fato, o algoritmo ganancioso para Max-Cut com aproximação de é o mesmo que o algoritmo "método das expectativas condicionais" para Max-Cut com aproximação de ).x i 1 / 2 1 /$i=1,\ldots,n$$x_i$$1/2$$1/2$

Como o método também funciona para o Max-E3-SAT e atinge uma aproximação de , este é um exemplo de um algoritmo ganancioso que é uma aproximação ideal, a menos que (cf. resultados de inadequação de Hastad e Moshkovitz-Raz para Max- E3-SAT).P = N $7/8$$P=NP$

Cobertura de vértices: O melhor algoritmo de aproximação de fator constante envolve (avidamente) encontrar uma correspondência máxima e escolher todos os vértices envolvidos como a solução aproximada. Isso gera uma solução aproximada de 2 e nenhuma melhor aproximação de fator constante é possível , a menos que a conjectura de jogos exclusivos seja falsa.

Subhash Khot e Oded Regev, a cobertura do Vertex pode ser difícil de aproximar de 2 ε , JCSS 74 (3), 2008.

Fora do tópico: Eu acho que esse é um algoritmo de aproximação muito bonito, especialmente porque é tão trivial com o benefício da retrospectiva.

Dado um gráfico direcionado, encontre o subgrafo acíclico com número máximo de arestas.

Algoritmo trivial de 2 aproximações: escolha uma ordem arbitrária dos vértices e pegue as arestas dianteiras ou traseiras.

Sabe-se que vencer a aproximação de 2 é difícil para os jogos exclusivos (embora possa não ser difícil para o NP).

• É difícil vencer a ordem aleatória: Inaproximabilidade do subgrafo acíclico máximo Venkatesan Guruswami, Rajsekar Manokaran e Prasad Raghavendra.

A maximização submodular com relação à restrição de cardinalidade tem uma aproximação gulosa de 1-1 / e. O algoritmo é devido a Nemhauser, Wolsey, Fisher. A dureza NP resulta da dureza np da tampa do conjunto, pois a cobertura máxima é um caso especial de maximização submodular.

Greedy fornece uma aproximação (1-1 / e) a Max-k-cover, e isso não pode ser melhorado a menos que P = NP.

Encontrando um grau mínimo MST. É difícil, pois encontrar um caminho hamiltoniano é um caso especial. Um algoritmo de busca local fornece dentro de uma constante aditiva 1.

Referência

Aproximar a árvore Steiner de grau mínimo a uma das condições ideais

$k$$G = (V,E)$$d_{ij} \geq 0$$i,j \in V$$k$

$k$$S \subseteq V, |S| = k$$k$$k$$k$$r$$r$

$i \in V$$S$$|S| < k$$j \in V$$d(j,S)$$S$$|S| = k$

$2$$k$$\rho$$\rho < 2$$P = NP$$k$$k$$2$

$P|prec|C_{max}$

Programação condicional de dureza condicional de precedência em máquinas idênticas por Ola Svensson

Talvez isso também lhe interesse (adaptado de Métodos para converter restrições globais em restrições locais )

Como os métodos gananciosos (métodos locais mais corretamente ) empregam apenas informações locais para obter otimização global, se forem encontradas formas capazes de transformar condições globais em condições capazes de serem usadas empregando apenas informações locais, isso fornece uma solução (globalmente) ideal para os problemas usando apenas técnicas gananciosas / locais.

Referências:

1. Pense globalmente, ajuste localmente: aprendizado não supervisionado de coletores de baixa dimensão (Journal of Machine Learning Research 4 (2003))
2. Otimização global usando informações locais com aplicativos para controle de fluxo, Bartal, Y.
3. Por que Natural Gradient ?, Amari S., Douglas SC
4. Otimização local de objetivos globais: resolução de impasse distribuído competitivo e alocação de recursos, Awerbuch, Baruch, Azar, Y.
5. Aprendendo com consistência local e global
6. Problemas de satisfação com restrições solucionáveis ​​por métodos de consistência local

Existem algumas referências que abordam o problema de traduzir funções de avaliação global (ou restrições) para funções locais (usando informações locais) e sua consistência (isto é, convergência para o mesmo ótimo global):

1. Funções Locais de Avaliação e Funções Globais de Avaliação para Evolução Computacional, HAN Jing, 2003
2. Emergência da Função de Avaliação Local, Han Jing e Cai Qingsheng, 2002

Resumo (de 1. acima)

Este artigo apresenta um novo olhar sobre a evolução computacional a partir do aspecto da localidade e globalidade das funções de avaliação para resolver o problema combinatório clássico: o Problema kcoloring (problema de decisão) e o Problema Mínimo de Coloração (problema de otimização). Primeiro, revisamos os algoritmos atuais e modelamos o problema de coloração como um sistema multiagente. Em seguida, mostramos que a diferença essencial entre algoritmos tradicionais (Pesquisa Local, como Simulated Annealing) e algoritmos distribuídos (como o modelo Alife & AER) está na função de avaliação: O Simulated Annealing usa informações globais para avaliar todo o estado do sistema, chamado o método da função de avaliação global (GEF); o modelo Alife & AER usa informações locais para avaliar o estado de um único agente, chamado método de função de avaliação local (LEF). Comparamos o desempenho dos métodos LEF e GEF para resolver os problemas da coloração k e os problemas mínimos da coloração. Os resultados experimentais em computador mostram que a LEF é comparável aos métodos GEF (Simulated Annealing and Greedy); em muitos casos problemáticos, a LEF vence os métodos GEF. Ao mesmo tempo, analisamos a relação entre GEF e LEF: consistência e inconsistência. O Teorema da Consistência mostra que os Equilíbrios de Nash de um LEF são idênticos aos ótimos locais de um GEF quando o LEF é consistente com o GEF. Esse teorema explica em parte por que a LEF pode levar o sistema a um objetivo global. Algumas regras para a construção de uma LEF consistente são propostas. Além da consistência,

Especificamente, o artigo aborda métodos para determinar se uma função local (LEF) é consistente com uma função global (GEF) e métodos para construir LEFs consistentes a partir de determinados GEFs ( teorema da consistência ).

Trecho da seção Conclusão (de 1. acima)

Este artigo é apenas o começo dos estudos da LEF e GEF. Além do relatório de pesquisa acima, ainda há muitos trabalhos futuros: mais experimentos nos métodos LEF; estudo analítico sobre LEF; suficiência de informações locais para LEF; e a existência de um GEF consistente para qualquer LEF; O conceito de consistência é suficiente? Como os algoritmos genéticos também têm uma função de avaliação (função de condicionamento físico), podemos aplicar LEF e GEF aos algoritmos genéticos? … Nossa intenção é estudar e tentar responder a todas essas perguntas