Algoritmos de Aproximação

Visão geral

Muitos problemas de otimização que aparecem em sistemas de IA (AI)—cobertura, agrupamento, roteamento, alocação de recursos, compressão de modelos—são NP-difíceis (NP-hard). Para esses problemas, não esperamos algoritmos em tempo polinomial (polynomial time) que sempre retornem o ótimo exato (a menos que conjecturas importantes de teoria da complexidade falhem). Algoritmos de aproximação (approximation algorithms) são uma alternativa fundamentada:

  • Eles rodam em tempo polinomial.
  • Eles retornam soluções comprovadamente próximas do ótimo.
  • Suas garantias valem no pior caso (ou em expectativa para algoritmos randomizados).

Algoritmos de aproximação ficam entre algoritmos exatos (muitas vezes exponenciais) e heurísticas (muitas vezes rápidas, mas sem garantias). Eles são uma ferramenta central nas bases algorítmicas e também aparecem em pipelines modernos de aprendizado de máquina (machine learning) (por exemplo, objetivos de agrupamento, seleção de dados submodular (submodular) e relaxações de inferência discreta).

Problemas de otimização e razões de aproximação

Um problema de otimização tem:

  • Um conjunto de soluções viáveis (S)
  • Uma função objetivo (custo/valor) (f(S))
  • Um objetivo: minimizar (f(S)) ou maximizar (f(S))

Seja OPT o valor do objetivo de uma solução ótima.

Garantias multiplicativas de aproximação

A maioria dos resultados clássicos usa garantias multiplicativas.

Minimização

Um algoritmo é uma (\rho)-aproximação (para (\rho \ge 1)) se, para toda instância:

[ f(\text{ALG}) \le \rho \cdot \text{OPT}. ]

Exemplo: uma 2-aproximação para Cobertura de Vértices (Vertex Cover) sempre retorna uma cobertura de tamanho no máximo (2\cdot) o ótimo.

Maximização

Duas formas equivalentes são comuns:

  • (f(\text{ALG}) \ge \alpha \cdot \text{OPT}) (com (0 < \alpha \le 1)), ou
  • ( \frac{\text{OPT}}{f(\text{ALG})} \le \rho ) (com (\rho \ge 1), onde (\alpha = 1/\rho)).

Exemplo: Goemans–Williamson fornece ~0.878-aproximação para Corte Máximo (Max-Cut).

Garantias aditivas e garantias bicritério

Alguns problemas naturalmente usam:

  • Erro aditivo: (f(\text{ALG}) \le \text{OPT} + \varepsilon)
  • Aproximações bicritério: permitem violar levemente uma restrição para ganhar qualidade no objetivo (comum em agrupamento e escalonamento)

O que “tempo polinomial” realmente significa na prática

Algoritmos de aproximação frequentemente são polinomiais, mas podem esconder constantes grandes (por exemplo, resolução de PL/PSD, ou tempos de um PTAS como (n^{O(1/\varepsilon)})). Em sistemas reais, praticantes às vezes usam uma aproximação mais simples de fator constante como baseline confiável e, em seguida, refinam com melhorias locais.

Esquemas de aproximação: PTAS e FPTAS

Um objetivo central é chegar arbitrariamente perto do ótimo.

  • Esquema de aproximação em tempo polinomial (PTAS, Polynomial-Time Approximation Scheme): para qualquer (\varepsilon > 0), retorna uma solução ((1+\varepsilon))-aproximada (minimização) em tempo polinomial em (n) para (\varepsilon) fixo. O tempo de execução pode ser (n^{g(1/\varepsilon)}).
  • Esquema de aproximação totalmente em tempo polinomial (FPTAS, Fully Polynomial-Time Approximation Scheme): tempo de execução polinomial tanto em (n) quanto em (1/\varepsilon).

Exemplo clássico: Mochila 0/1 (0/1 Knapsack) tem um FPTAS.

Esquemas de aproximação são poderosos, mas muitos problemas comprovadamente não admitem um PTAS a menos que (P=NP) (ou sob suposições mais fortes), e alguns são APX-difíceis (APX-hard), isto é, existe uma barreira de fator constante.

Limites fundamentais: não-aproximabilidade

Aproximar não é “de graça”: para muitos problemas NP-difíceis, até mesmo aproximar dentro de certos fatores é NP-difícil.

Ideias importantes (em alto nível):

  • Reduções com lacuna (gap reductions): reduzir de um problema de decisão para mostrar que distinguir “OPT é pequeno” vs “OPT é grande” é NP-difícil, implicando dureza de aproximação.
  • Teorema PCP (PCP theorem): implica forte não-aproximabilidade para muitos problemas de satisfação de restrições (constraint satisfaction problems).
  • Resultados conhecidos quase-justos:
    • Cobertura de Conjuntos (Set Cover): não pode ser aproximado melhor que ((1-o(1))\ln n) a menos que (P=NP); o algoritmo guloso (greedy) alcança (H_n \approx \ln n + \gamma).
    • Cobertura de Vértices: 2-aproximação é fácil; melhorar abaixo de 2 é considerado difícil (há resultados condicionais de dureza, por exemplo, sob a Conjectura dos Jogos Únicos (Unique Games Conjecture)).

Na prática, essas barreiras guiam expectativas: se a teoria diz que (\ln n) é essencialmente ótimo, você para de buscar uma garantia de fator constante e ou aceita isso, ou muda a formulação do problema.

Técnicas comuns de análise

Provas de aproximação frequentemente reutilizam um pequeno conjunto de “movimentos”:

  • Argumentos de cobrança (charging arguments): atribuem (cobram) o custo das escolhas do algoritmo a elementos de OPT.
  • Relaxar e arredondar (relax-and-round): resolve uma relaxação (PL/PSD), depois arredonda para uma solução integral limitando a perda.
  • Lacuna de integralidade (integrality gap): compara a melhor solução integral com a melhor solução relaxada; frequentemente dita a melhor garantia possível usando aquela relaxação.
  • Ajuste do dual / primal–dual (dual fitting / primal–dual): constrói uma solução dual viável ao longo do caminho para limitar OPT inferiormente.
  • Análise por função potencial (potential-function analysis) (frequente em busca local): mostra que cada movimento local melhora um potencial e que um ótimo local está globalmente perto do ótimo.

Essas técnicas reaparecem em problemas próximos de IA, como relaxações para inferência MAP (MAP inference), agrupamento e objetivos de localização de facilidades (facility location).

Padrões de projeto para algoritmos de aproximação

Métodos gulosos

Algoritmos gulosos fazem escolhas localmente ótimas. Sozinhos, podem falhar muito, mas com a estrutura certa produzem garantias fortes.

O método guloso é especialmente eficaz para:

  • Problemas de cobertura (por exemplo, Cobertura de Conjuntos)
  • Otimização submodular, comum em sumarização de dados e aprendizado ativo, onde retornos decrescentes permitem limites demonstráveis

Veja também: Algoritmos Gulosos.

Relaxação de PL e arredondamento

Muitos problemas NP-difíceis têm programas inteiros (IP, integer programs) naturais. Relaxe as restrições de integralidade para obter uma programação linear (PL, LP), resolva-a eficientemente e depois arredonde a solução fracionária.

Ferramentas comuns de arredondamento:

  • Arredondamento por limiar (por exemplo, escolher variáveis com (x_i \ge 1/2))
  • Arredondamento randomizado (escolher (i) com probabilidade (x_i))
  • Arredondamento dependente (manter restrições como cardinalidade)

A aproximação baseada em PL é amplamente usada porque solucionadores de PL são maduros e robustos.

Métodos primal–dual

Algoritmos primal–dual constroem simultaneamente:

  • uma solução viável primal (a saída de fato), e
  • uma solução viável dual (um certificado que limita OPT inferiormente)

Eles frequentemente são simples, combinatórios e rápidos—úteis quando resolver uma PL seria caro.

Busca local

A busca local (local search) começa de qualquer solução viável e aplica repetidamente melhorias locais (movimentos de troca/adição/remoção) até não existir melhoria.

  • Fácil de implementar
  • Muitas vezes excelente na prática
  • Mais difícil de analisar, mas existem muitos resultados clássicos (notadamente em variantes de agrupamento)

Esquemas de aproximação via escalonamento e programação dinâmica

Alguns problemas admitem um algoritmo exato pseudo-polinomial (frequentemente via Programação Dinâmica). Com escalonamento/arredondamento de pesos ou valores, você pode converter isso em um FPTAS.

Programação semidefinida (SDP)

Relaxações por programação semidefinida (SDP, semidefinite programming) podem superar garantias baseadas em PL para certos problemas (por exemplo, Corte Máximo). PSDs são computacionalmente mais pesadas, mas ainda relevantes na teoria e em algumas aplicações de alto valor.

Exemplo clássico: Cobertura de Conjuntos (aproximação \(\ln n\) via guloso)

Problema

Dado um universo (U) de (n) elementos e uma coleção de subconjuntos (\mathcal{S} = {S_1, \dots, S_m}) com custos (c_i), escolha conjuntos cuja união seja (U) com custo total mínimo.

Isso modela tarefas como:

  • selecionar um conjunto mínimo de “características/testes” que cobre requisitos,
  • escolher um pequeno conjunto de exemplos de treinamento que “cobre” comportamentos,
  • implantar sensores para cobrir regiões.

Algoritmo guloso (ponderado)

Repetidamente escolha o conjunto com menor custo por elemento recém-coberto.

Greedy-Set-Cover(U, S, c):
  C = ∅
  uncovered = U
  while uncovered ≠ ∅:
    choose S_i minimizing c_i / |S_i ∩ uncovered|
    C = C ∪ {S_i}
    uncovered = uncovered \ S_i
  return C

Garantia

O guloso alcança uma (H_n)-aproximação, onde (H_n = 1 + 1/2 + \dots + 1/n \approx \ln n).

Ideia da prova (argumento de cobrança): Cobre-se (cobra-se) de cada elemento recém-coberto um valor igual ao “preço por elemento descoberto” do conjunto escolhido. Mostra-se que nenhum elemento é supercobrado demais em relação a OPT, resultando no limite harmônico.

Observações práticas

  • O guloso é simples e escala bem.
  • Funciona como um baseline forte mesmo quando você depois adiciona melhorias locais.
  • Em pipelines de aprendizado de máquina, cobertura de conjuntos frequentemente aparece de forma disfarçada (por exemplo, selecionar um pequeno conjunto de restrições, prompts, testes ou exemplos para cobrir um conjunto de comportamentos).

Exemplo clássico: Cobertura de Vértices (arredondamento de PL dá 2-aproximação)

Problema

Dado um grafo não direcionado (G=(V,E)), escolha o menor conjunto de vértices (C \subseteq V) tal que toda aresta tenha pelo menos uma extremidade em (C).

Cobertura de vértices é um bloco de construção em muitas reduções e aparece em alocação de recursos e monitoramento de redes.

Relaxação de PL

Programa inteiro:

  • Variável (x_v \in {0,1}) para cada vértice (v)
  • Para cada aresta ((u,v)): (x_u + x_v \ge 1)
  • Minimizar (\sum_v x_v)

Relaxe para (x_v \in [0,1]), resolva a PL de forma ótima e então arredonde:

LP-Round-Vertex-Cover(G):
  solve LP to get x_v ∈ [0,1]
  return C = { v : x_v ≥ 1/2 }

Garantia (2-aproximação)

Para qualquer aresta ((u,v)), a restrição implica (x_u + x_v \ge 1), então pelo menos uma extremidade tem (x \ge 1/2); logo, o conjunto arredondado é viável.

Para o objetivo: [ |C| \le 2\sum_v x_v \le 2\cdot \text{OPT} ] porque selecionar todos os (v) com (x_v \ge 1/2) multiplica cada variável selecionada por no máximo 2.

Observações práticas

  • Este é um template canônico de “PL + arredondamento simples”.
  • Na prática, resolver a PL para grafos muito grandes pode ser pesado; também há 2-aproximações rápidas via emparelhamento maximal (maximal matching):
    • tome um emparelhamento maximal (M),
    • retorne ambas as extremidades das arestas em (M),
    • obtém uma 2-aproximação sem PL.

Exemplo clássico: variantes de Mochila (guloso, PD, FPTAS)

Mochila fracionária (resolvível exatamente por guloso)

Dado itens com valor (v_i), peso (w_i), capacidade (W). Você pode pegar frações de itens. Ordene pela densidade de valor (v_i/w_i) e pegue o máximo possível—isso é ótimo.

Isso importa porque fornece:

  • um baseline rápido,
  • um limite ou relaxação para mochila 0/1.

Mochila 0/1 (NP-difícil, admite FPTAS)

Na mochila 0/1, cada item é tomado por inteiro ou não é tomado. Há uma programação dinâmica pseudo-polinomial clássica:

  • Seja (V = \sum_i v_i)
  • PD sobre o valor total: peso mínimo necessário para atingir um dado valor

Isso é exato em (O(nV)), o que é grande demais se os valores forem grandes. O FPTAS escala valores:

  1. Escolha um fator de escala (K = \varepsilon \cdot V_{\max}/n)
  2. Substitua (v_i) por (v'_i = \lfloor v_i / K \rfloor)
  3. Execute a PD em (v'_i), cuja soma agora é (O(n^2/\varepsilon))

Resultado: uma ((1-\varepsilon))-aproximação (maximização) em tempo polinomial em (n) e (1/\varepsilon).

Observações práticas

  • Restrições do tipo mochila aparecem em aprendizado de máquina como seleção com orçamento (budgeted selection) (escolher características, tarefas de rotulagem, experimentos ou componentes de modelo sob orçamentos de memória/latência).
  • FPTAS é atraente quando você precisa de uma troca ajustável entre precisão e tempo de execução.

Exemplos adicionais notáveis (breve)

  • Problema do Caixeiro Viajante métrico (Metric TSP): com desigualdade triangular (triangle inequality), o algoritmo de Christofides (Christofides’ algorithm) fornece uma 1.5-aproximação (clássico em roteamento/logística).
  • Agrupamento k-centro (k-center clustering): a varredura do mais distante primeiro (farthest-first traversal) fornece uma 2-aproximação em espaços métricos; isso se conecta diretamente a agrupamento em aprendizado de máquina.
  • Corte Máximo: Goemans–Williamson baseado em PSD alcança ~0.878-aproximação, um resultado marco que ilustra como relaxações mais fortes melhoram fatores.

Eles destacam um tema importante: a estrutura importa. Adicionar suposições métricas ou relaxar restrições pode transformar o que é aproximável.

Por que algoritmos de aproximação importam na prática de IA/aprendizado de máquina

Mesmo quando o modelo principal é aprendido, muitos cálculos ao redor são combinatórios:

  • Agrupamento e sumarização
    • objetivos k-centro/k-mediana (k-median) em sumarização de datasets e construção de subconjuntos representativos (coreset)
    • objetivos submodulares do tipo localização de facilidades para selecionar pontos representativos
  • Inferência discreta
    • inferência MAP em Modelos Gráficos frequentemente é NP-difícil; relaxações de PL/PSD e arredondamento são padrão
  • Seleção de características e prompts sob restrições
    • seleção com orçamento frequentemente se reduz a formulações do tipo mochila
  • Cobertura e testes
    • selecionar suítes de teste ou prompts de avaliação para cobrir comportamentos se assemelha a cobertura de conjuntos / conjunto de interseção (hitting set)
  • Escalonamento e alocação de recursos
    • jobs de treinamento, GPUs e etapas de pipeline podem produzir variantes NP-difíceis de escalonamento, onde aproximação fornece baselines seguros

Um modelo mental útil: algoritmos de aproximação fornecem “guarda-corpos” confiáveis. Você pode começar com um baseline demonstrável e então incorporar heurísticas de domínio (ou previsões de aprendizado de máquina) por cima, ainda entendendo o comportamento no pior caso.

Orientação prática: escolhendo uma abordagem

Quando você enfrenta um subproblema NP-difícil de otimização em um sistema de IA, um fluxo de trabalho comum é:

  1. Verificar estrutura especial
    • métrico? submodular? bipartido? restrições totalmente unimodulares?
  2. Tentar um template conhecido de aproximação
    • guloso para cobertura/submodular
    • relaxação de PL + arredondamento para problemas de decisão binária
    • primal–dual para sabores de projeto de redes / localização de facilidades
    • busca local para objetivos do tipo agrupamento
  3. Decidir o ponto de “garantia vs velocidade”
    • algoritmos de fator constante muitas vezes são muito rápidos e robustos
    • PTAS/FPTAS podem ser ótimos se os tamanhos das instâncias permitirem e você precisar de precisão
  4. Usar a relaxação como ferramenta de diagnóstico
    • a PL fornece um limite inferior para OPT; a lacuna em relação à sua solução é informação acionável

Relação com heurísticas e métodos aumentados por aprendizado

Algoritmos de aproximação não são anti-heurística; eles complementam heurísticas:

  • Heurísticas podem ser excelentes em instâncias típicas, mas falhar catastroficamente.
  • Algoritmos de aproximação dão uma garantia de pior caso e muitas vezes um certificado/limite inferior claro via relaxações.

Uma direção crescente são algoritmos aumentados por aprendizado (learning-augmented algorithms), onde aprendizado de máquina prevê boas escolhas (por exemplo, conjuntos promissores, decisões de arredondamento, movimentos de busca local) enquanto o algoritmo retém um fallback demonstrável ou uma garantia de robustez. Isso é atraente em IA de produção: você obtém velocidade/qualidade empírica do aprendizado, além de redes de segurança teóricas.

Principais conclusões

  • Algoritmos de aproximação fornecem soluções em tempo polinomial para problemas NP-difíceis de otimização com garantias de qualidade demonstráveis.
  • A principal garantia é uma razão de aproximação (approximation ratio), sustentada por técnicas como argumentos de cobrança, relaxações de PL/PSD, análise primal–dual e provas de busca local.
  • Resultados clássicos:
    • Cobertura de Conjuntos: guloso dá (\Theta(\log n))-aproximação (essencialmente o melhor possível).
    • Cobertura de Vértices: arredondamento simples de PL (ou emparelhamento) dá 2-aproximação.
    • Mochila: admite um FPTAS via escalonamento + programação dinâmica.
  • Em sistemas de IA/aprendizado de máquina, algoritmos de aproximação são amplamente relevantes para agrupamento, inferência discreta, seleção com orçamento e alocação de recursos—muitas vezes servindo como baselines fortes com garantias interpretáveis.