Aproximações com garantia

Fator e prova

Minimização com custos positivos: $C\le\rho OPT$. Maximização: $C\ge OPT/\rho$. Precisa de admissível sempre e tempo polinomial. Heurística sem limite não é aproximação.

Problema	Regra	Garantia	Hipótese que decide
Cobertura de vértices	Repetir até não haver aresta descoberta; incluir os dois extremos	$C\le2OPT$	Arestas escolhidas formam emparelhamento maximal; cada aresta de $OPT$ cobre no máximo duas
Mochila	Melhor entre prefixo por densidade e maior objeto isolado	$C\ge OPT/2$	Descarta cada objeto que não cabe; o limite fracionário ordenado por densidade sustenta a prova
TSP	Duplicar MST e atalhar	$C\le2OPT$	Completo, simétrico, não negativos, triangular
Conjuntos	Maior ganho por passo	$C\le H_dOPT$	$d$ é o tamanho do maior conjunto; $H_d=1+1/2+\dots+1/d$

Erros que partem garantias

• Uma aresta isolada não garante cobertura: com duas arestas disjuntas, escolher só uma deixa a outra descoberta. O algoritmo repete a escolha até não restar aresta com os dois extremos fora da cobertura, e só então as arestas escolhidas formam um emparelhamento maximal.
• Só o prefixo por densidade falha: com objetos (6,12), (5,9) e (5,9) e $W=10$, a densidade escolhe 12 mas o par seguinte dá 18. Comparar com o melhor objeto isolado repõe o fator 2.
• TSP sem triangularidade ou com dirigidas assimétricas invalida atalhos.
• Somar $M$ a cada aresta de TSP com $n$ cidades conserva ótimos mas muda razões: $C+nM\le2(OPT+nM)$ só dá $C\le2OPT+nM$.
• PTAS é polinomial na entrada para $\varepsilon$ fixo; FPTAS também em $1/\varepsilon$.

Execução e provas.