Algoritmo de aproximação - Approximation algorithm

Em ciência da computação e operações de investigação , algoritmos de aproximação são eficientes algoritmos que encontram aproximados soluções para problemas de otimização (em particular NP-difíceis problemas) com garantias demonstráveis sobre a distância da solução retornado ao ideal um. Os algoritmos de aproximação surgem naturalmente no campo da ciência da computação teórica como conseqüência da conjectura P ≠ NP amplamente aceita . Sob essa conjectura, uma ampla classe de problemas de otimização não pode ser resolvida exatamente em tempo polinomial . O campo dos algoritmos de aproximação, portanto, tenta entender o quão próximo é possível aproximar soluções ótimas para tais problemas em tempo polinomial. Na esmagadora maioria dos casos, a garantia de tais algoritmos é multiplicativa expressa como uma razão de aproximação ou fator de aproximação, ou seja, a solução ótima é sempre garantida estar dentro de um fator multiplicativo (predeterminado) da solução retornada. No entanto, também existem muitos algoritmos de aproximação que fornecem uma garantia aditiva sobre a qualidade da solução retornada. Um exemplo notável de um algoritmo de aproximação que fornece ambos é o algoritmo de aproximação clássico de Lenstra , Shmoys e Tardos para agendamento em máquinas paralelas não relacionadas .

O projeto e a análise de algoritmos de aproximação envolvem crucialmente uma prova matemática que certifica a qualidade das soluções retornadas no pior caso. Isso os distingue de heurísticas , como recozimento ou algoritmos genéticos , que encontram soluções razoavelmente boas em algumas entradas, mas não fornecem nenhuma indicação clara no início sobre quando eles podem ter sucesso ou falhar.

Há amplo interesse na ciência da computação teórica para entender melhor os limites aos quais podemos nos aproximar de certos famosos problemas de otimização. Por exemplo, uma das questões em aberto de longa data na ciência da computação é determinar se há um algoritmo que supere o algoritmo de aproximação 1,5 de Christofides para o problema do caixeiro viajante métrico . O desejo de entender os problemas de otimização difícil da perspectiva da aproximabilidade é motivado pela descoberta de conexões matemáticas surpreendentes e técnicas amplamente aplicáveis ​​para projetar algoritmos para problemas de otimização rígida. Um exemplo bem conhecido do primeiro é o algoritmo Goemans – Williamson para corte máximo , que resolve um problema teórico de grafos usando geometria de alta dimensão.

Introdução

Um exemplo simples de algoritmo de aproximação é aquele para o problema de cobertura de vértices mínimos , onde o objetivo é escolher o menor conjunto de vértices de forma que cada aresta no gráfico de entrada contenha pelo menos um vértice escolhido. Uma maneira de encontrar uma cobertura de vértice é repetir o seguinte processo: encontre uma aresta descoberta, adicione seus pontos finais à cobertura e remova todas as arestas incidentes em cada vértice do gráfico. Como qualquer cobertura de vértice do grafo de entrada deve usar um vértice distinto para cobrir cada aresta que foi considerada no processo (uma vez que forma uma correspondência ), a cobertura de vértice produzida, portanto, é no máximo duas vezes maior que a ótima. Em outras palavras, este é um algoritmo de aproximação de fator constante com um fator de aproximação de 2. De acordo com a recente conjectura de jogos exclusivos , este fator é mesmo o melhor possível.

Os problemas NP-difíceis variam muito em sua aproximação; alguns, como o problema da mochila , podem ser aproximados dentro de um fator multiplicativo , para qualquer fixo e, portanto, produzem soluções arbitrariamente próximas do ótimo (tal família de algoritmos de aproximação é chamada de esquema de aproximação de tempo polinomial ou PTAS). Outros são impossíveis de se aproximar dentro de qualquer fator constante, ou mesmo polinomial, a menos que P = NP , como no caso do problema de clique máximo . Portanto, um benefício importante de estudar algoritmos de aproximação é uma classificação refinada da dificuldade de vários problemas NP-difíceis além do oferecido pela teoria da NP-completude . Em outras palavras, embora os problemas NP-completos possam ser equivalentes (sob reduções de tempo polinomial) entre si da perspectiva de soluções exatas, os problemas de otimização correspondentes se comportam de maneira muito diferente da perspectiva de soluções aproximadas.

Técnicas de projeto de algoritmo

Atualmente, existem várias técnicas estabelecidas para projetar algoritmos de aproximação. Isso inclui os seguintes.

  1. Algoritmo ganancioso
  2. Pesquisa local
  3. Enumeração e programação dinâmica
  4. Resolvendo uma relaxação de programação convexa para obter uma solução fracionária. Em seguida, converter essa solução fracionária em uma solução viável por alguns arredondamentos apropriados. Os relaxamentos populares incluem o seguinte.
  5. Métodos primários-duais
  6. Encaixe duplo
  7. Incorporar o problema em alguma métrica e, em seguida, resolver o problema na métrica. Isso também é conhecido como incorporação de métricas.
  8. Amostragem aleatória e o uso da aleatoriedade em geral em conjunto com os métodos acima.

Garantias a posteriori

Embora os algoritmos de aproximação sempre forneçam uma garantia a priori do pior caso (seja ela aditiva ou multiplicativa), em alguns casos eles também fornecem uma garantia a posteriori que geralmente é muito melhor. Esse é frequentemente o caso de algoritmos que funcionam resolvendo um relaxamento convexo do problema de otimização na entrada fornecida. Por exemplo, existe um algoritmo de aproximação diferente para cobertura mínima de vértice que resolve uma relaxação de programação linear para encontrar uma cobertura de vértice que é no máximo duas vezes o valor da relaxação. Uma vez que o valor da relaxação nunca é maior do que o tamanho da cobertura ótima do vértice, isso produz outro algoritmo de 2 aproximações. Embora isso seja semelhante à garantia a priori do algoritmo de aproximação anterior, a garantia do último pode ser muito melhor (de fato, quando o valor da relaxação LP está longe do tamanho da cobertura do vértice ideal).

Dureza de aproximação

Os algoritmos de aproximação como área de pesquisa estão intimamente relacionados e informados pela teoria da improximabilidade, onde a inexistência de algoritmos eficientes com certas razões de aproximação é comprovada (condicionada a hipóteses amplamente aceitas, como a conjectura P ≠ NP) por meio de reduções . No caso do problema do caixeiro viajante métrico, o resultado de improximabilidade mais conhecido descarta algoritmos com uma razão de aproximação menor que 123/122 ≈ 1,008196 a menos que P = NP, Karpinski, Lampis, Schmied. Juntamente com o conhecimento da existência do algoritmo de aproximação 1,5 de Christofides, isso nos diz que o limite de aproximabilidade para o caixeiro viajante métrico (se existir) está em algum lugar entre 123/122 e 1,5.

Embora os resultados de imprevisibilidade tenham sido provados desde a década de 1970, tais resultados foram obtidos por meios ad hoc e nenhum entendimento sistemático estava disponível na época. Foi somente a partir do resultado de Feige, Goldwasser, Lovász, Safra e Szegedy sobre a não-aproximabilidade de Conjunto Independente e o famoso teorema PCP , que ferramentas modernas para provar resultados de incompatibilidade foram descobertas. O teorema PCP, por exemplo, mostra que de Johnson 1974 algoritmos de aproximação para Max sab , tampa conjunto , conjunto independente e colorir toda a conseguir a proporção aproximação óptima, assumindo P ≠ NP.

Praticidade

Nem todos os algoritmos de aproximação são adequados para aplicações práticas diretas. Alguns envolvem a solução de programação linear não trivial / relaxamentos semidefinidos (que podem eles próprios invocar o algoritmo elipsóide ), estruturas de dados complexas ou técnicas algorítmicas sofisticadas, levando a problemas de implementação difíceis ou desempenho de tempo de execução aprimorado (sobre algoritmos exatos) apenas em entradas impraticavelmente grandes . Deixando de lado as questões de implementação e tempo de execução, as garantias fornecidas pelos algoritmos de aproximação podem não ser fortes o suficiente para justificar sua consideração na prática. Apesar de sua incapacidade de ser usado "fora da caixa" em aplicações práticas, as idéias e os insights por trás do design de tais algoritmos podem frequentemente ser incorporados de outras maneiras em algoritmos práticos. Desse modo, o estudo de algoritmos mesmo muito caros não é uma busca completamente teórica, pois eles podem gerar insights valiosos.

Em outros casos, mesmo que os resultados iniciais sejam de interesse puramente teórico, ao longo do tempo, com um melhor entendimento, os algoritmos podem ser refinados para se tornarem mais práticos. Um exemplo é o PTAS inicial para Euclidean TSP por Sanjeev Arora (e independentemente por Joseph Mitchell ) que tinha um tempo de execução proibitivo de para uma aproximação. No entanto, dentro de um ano, essas ideias foram incorporadas a um algoritmo de tempo quase linear para qualquer constante .

Garantias de desempenho

Para alguns algoritmos de aproximação, é possível provar certas propriedades sobre a aproximação do resultado ótimo. Por exemplo, um algoritmo de aproximação de ρ A é definido como um algoritmo para o qual foi provado que o valor / custo, f ( x ), da solução aproximada A ( x ) para uma instância x não será maior (ou menos, dependendo da situação) do que um fator ρ vezes o valor, OPT, de uma solução ótima.

O fator ρ é chamado de garantia de desempenho relativo . Um algoritmo de aproximação tem uma garantia de desempenho absoluta ou erro limitado c , se tiver sido provado para cada instância x que

Da mesma forma, a garantia de desempenho , R ( x, y ), de uma solução y para uma instância x é definida como

onde f ( y ) é o valor / custo da solução y para a instância x . Claramente, a garantia de desempenho é maior ou igual a 1 e igual a 1 se e somente se y for uma solução ótima. Se um algoritmo A garantias para retornar soluções com uma garantia de execução de, no máximo, r ( n ), então A é dito ser um r ( n ) -approximation algoritmo e tem uma razão de aproximação de r ( n ). Da mesma forma, um problema com um algoritmo de aproximação de r ( n ) é dito ser r ( n ) - aproximado ou tem uma razão de aproximação de r ( n ).

Para problemas de minimização, as duas garantias diferentes fornecem o mesmo resultado e para problemas de maximização, uma garantia de desempenho relativa de ρ é equivalente a uma garantia de desempenho de . Na literatura, ambas as definições são comuns, mas é claro qual definição é usada, uma vez que, para problemas de maximização, como ρ ≤ 1 enquanto r ≥ 1.

A garantia de desempenho absoluta de algum algoritmo de aproximação A , onde x se refere a uma instância de um problema, e onde está a garantia de desempenho de A em x (ou seja, ρ para a instância do problema x ) é:

Isso quer dizer que é o maior limite na razão de aproximação, r , que se vê em todas as instâncias possíveis do problema. Da mesma forma, a proporção de desempenho assintótico é:

Isso quer dizer que é o mesmo que a taxa de desempenho absoluta , com um limite inferior n no tamanho das instâncias do problema. Esses dois tipos de proporções são usados ​​porque existem algoritmos em que a diferença entre os dois é significativa.

Garantias de desempenho
r -approx ρ -approx rel. erro rel. erro norma. rel. erro abdômen. erro
max:
min:

Termos Epsilon

Na literatura, uma razão de aproximação para um problema de maximização (minimização) de c - ϵ (min: c + ϵ) significa que o algoritmo tem uma razão de aproximação de c ∓ ϵ para ϵ> 0 arbitrário, mas que a razão não tem (ou não pode) ser mostrado para ϵ = 0. Um exemplo disso é a inadequação ótima - inexistência de aproximação - razão de 7/8 + ϵ para instâncias MAX-3SAT satisfatórias devido a Johan Håstad . Como mencionado anteriormente, quando c = 1, diz-se que o problema tem um esquema de aproximação de tempo polinomial .

Um termo ϵ pode aparecer quando um algoritmo de aproximação introduz um erro multiplicativo e um erro constante enquanto o ótimo mínimo de instâncias de tamanho n vai para o infinito como n . Nesse caso, a razão de aproximação é ck / OPT = c ∓ o (1) para algumas constantes c e k . Dado ε arbitrária> 0, pode-se escolher um grande o suficiente N tal que o termo k / OPT <ε para cada n ≥ N . Para cada ϵ fixo, instâncias de tamanho n <N podem ser resolvidas por força bruta, mostrando assim uma razão de aproximação - existência de algoritmos de aproximação com garantia - de c ∓ ϵ para todo ϵ> 0.

Veja também

Citações

Referências

links externos