Algoritmos de aproximação usados ​​em algoritmos exatos

Algoritmos de aproximação podem gerar um fator constante na saída. Isso é um pouco menos satisfatório do que algoritmos exatos.

No entanto, fatores constantes são ignorados na complexidade do tempo.

Então, eu me pergunto se o seguinte truque é possível ou foi usado, para resolver algum problema :$B \circ A$

1. Use um algoritmo de aproximação que resolva o problema para obter a solução S dentro do fator constante;$A$$S$
2. Use um algoritmo exato, resolvendo o problema , cujo tempo de execução depende do peso de S, mas funciona desde que S seja uma solução correta.$B$$S$$S$

Dessa forma, a aproximação é um "subprocedimento" de um algoritmo exato, e o fator constante perdido na etapa 1 é engolido na etapa 2.

Um exemplo da complexidade parametrizada é uma kernelização para o problema de cobertura de vértices usando um teorema de Nemhauser e Trotter.

No problema da cobertura mínima de vértices, recebemos um gráfico G não direcionado e precisamos encontrar uma cobertura de vértice G de tamanho mínimo. Uma capa de vértice de um gráfico não direcionado é um subconjunto de vértices que toca todas as arestas.

Aqui está um algoritmo exato que usa uma aproximação na primeira fase.

Fase 1: configure a formulação de programação linear inteira do problema mínimo de cobertura de vértices . Sabe-se (ou é fácil de mostrar) que uma solução ótima básica do relaxamento de programação linear é semi-integral (ou seja, todas as coordenadas são 0, 1 ou 1/2). Essa solução ótima básica pode ser encontrada por um algoritmo de tempo polinomial usual para programação linear (ou nesse caso especial, podemos formulá-lo como um problema de fluxo de rede, para que possamos resolvê-lo combinatoriamente em tempo polinomial). Tendo uma solução ótima básica, a arredondamos para obter uma solução viável para o problema de programação linear inteira original. Seja S o subconjunto de vértices correspondente. É bom observar que S é uma aproximação 2 da instância de cobertura mínima fornecida.

Fase 2: encontre uma cobertura mínima de vértices no subgráfico induzido por S (por exemplo, por uma pesquisa exaustiva). Um teorema de Nemhauser e Trotter afirma que este subgrafo contém uma solução ótima do gráfico de entrada original. Portanto, a correção dessa abordagem segue.

Você pode consultar um livro de Niedermeier sobre algoritmos de parâmetro fixo para esse algoritmo.

Um exemplo está relacionado a decomposições de árvores e gráficos de pequena largura de árvore.

$B$

$B$$A$

$A$$A$$A$$A$$B$

$B$$A$

$B$$A$$A$$B$

Um exemplo de um algoritmo de aproximação que converge para a solução exata seria o algoritmo elipsóide para resolver LPs - se os coeficientes forem racionais, será possível calcular uma distância mínima entre dois vértices do polítopo viável. Agora, o algoritmo elipsóide calcula repetidamente um elipsóide cada vez menor que deve conter a solução ideal. Uma vez que o eliposoide é pequeno o suficiente para conter apenas um único vértice, você basicamente encontrou o vértice ideal. É por isso que LP é fracamente polinomial.

$k$

Finalmente, ir além de um campo - muitos algoritmos que seguem a técnica de alteração (pegue uma amostra aleatória - e faça alguns reparos para conseguir o que deseja) se enquadra nesse quadro. Um exemplo bonito é o algoritmo para calcular a mediana usando amostragem aleatória (veja o livro de Motwani e Raghavan). Existem muitos exemplos - sem dúvida muitos dos algoritmos incrementais aleatórios em Geometria Computacional se enquadram nessa estrutura.

Muitos algoritmos sensíveis à saída empregam essa técnica. Por exemplo, aqui está um problema simples no qual essa técnica pode ser usada:

Problema . Você recebe uma matriz A [1 .. n ] na qual cada elemento está no máximo k posições distantes da posição em que estaria se A fosse classificado.

Por exemplo, A [1..7] mostrado abaixo pode ser uma matriz de entrada para k = 2.

Fonte do problema: Algo Muse Archive.