Aproximações com garantia

Na mochila de capacidade 10 com $A=(6,12)$, $B=(5,9)$ e $C=(5,9)$, escolher por densidade devolve valor 12, embora $B+C$ dê 18. Uma solução admissível pode ficar longe do ótimo. Para aceitar uma aproximação, precisamos de limitar essa distância para todas as entradas permitidas, não apenas neste exemplo.

Para minimização com custos positivos, um fator $\rho\ge1$ garante $C\le\rho OPT$. Para maximização, garante $C\ge OPT/\rho$. O algoritmo tem de produzir sempre uma solução admissível e correr em tempo polinomial. Uma heurística sem prova de limite não possui essa garantia, mesmo quando funciona bem em alguns casos.

Cobertura de vértices

Uma cobertura contém pelo menos um extremo de cada aresta. Escolhe uma aresta ainda não coberta, acrescenta os dois extremos e retira todas as arestas incidentes neles. Repete até não haver arestas.

Se escolhemos $ca$ na estrela, devolvemos $\{c,a\}$, tamanho 2. O centro $c$ sozinho cobre tudo, logo o ótimo vale 1. O fator 2 é atingido nesta instância, mas falta provar que nunca é excedido.

As arestas escolhidas formam um emparelhamento $M$: depois de escolher uma, retiramos todas as que partilham extremos com ela. Qualquer cobertura precisa de um vértice distinto para cada aresta de $M$, logo $OPT\ge |M|$. Devolvemos exatamente $2|M|$ vértices e cobrimos todas as arestas, portanto

$$C=2|M|\le2OPT.$$

Uma passagem pelas arestas, aceitando apenas as que ainda têm ambos os extremos fora da cobertura, implementa a regra em $O(n+m)$. Escolher o vértice de maior grau é outra heurística e não herda esta prova. Sem arestas, a cobertura vazia é ótima; a desigualdade mantém-se, embora o quociente por $OPT=0$ não esteja definido.

Escolher o maior grau não prova otimalidade

Liga um vértice c a quatro vértices $a_1,a_2,a_3,a_4$ e liga cada $a_i$ a duas folhas privadas, sem outras arestas. Inicialmente c tem grau 4, cada $a_i$ grau 3 e cada folha grau 1. A heurística de maior grau escolhe obrigatoriamente c. Depois ficam quatro estrelas de duas folhas, levando a escolher os quatro $a_i$. O resultado tem cinco vértices.

Escolher apenas $a_1,a_2,a_3,a_4$ cobre todas as arestas com quatro. Quatro também é um limite inferior: as quatro arestas entre cada $a_i$ e a sua primeira folha não partilham extremos. Logo o ótimo é quatro, e a heurística perdeu a otimalidade mesmo sem empate na primeira escolha. Este exemplo tem razão $5/4$; refuta a promessa de ótimo, mas não refuta sozinho uma garantia de fator 2. Para refutar essa garantia seria necessário um exemplo com razão superior a 2.

Mochila: prefixo e maior objeto

Assume pesos positivos e valores não negativos. Descarta objetos que não cabem sozinhos. Ordena os restantes por densidade decrescente e leva o prefixo até ao primeiro objeto $j$ que não cabe. Chama $P$ ao valor desse prefixo e $M$ ao maior valor de um objeto individual. Devolve a seleção com maior valor entre ambos, sem juntar as duas seleções.

Passo, com capacidade 10	Capacidade restante	Valor
Levar $A=(6,12)$, densidade 2	4	$P=12$
$B=(5,9)$ não cabe, densidade 1,8	4	Parar o prefixo
Melhor objeto individual	Peso 6	$M=12$ com $A$

O resultado é 12. O ótimo é 18 com $B+C$, por isso esta execução satisfaz $12\ge18/2$.

Para provar a garantia, permite frações. A solução fracionária ótima contém o prefixo e uma fração $\alpha\le1$ do primeiro objeto que não cabe. Como essa relaxação inclui todas as soluções 0-1,

$$OPT\le P+\alpha v_j\le P+v_j\le P+M.$$

Pelo menos um entre $P$ e $M$ vale metade da soma: $\max(P,M)\ge(P+M)/2\ge OPT/2$. Ambos correspondem a seleções válidas. Se todos os objetos cabem, o prefixo já é ótimo; se nenhum é elegível, o ótimo é zero. A ordenação custa $O(n\log n)$.

A prova usa o prefixo antes do primeiro objeto omitido. Continuar a experimentar os seguintes pode melhorar o resultado, mas o limite fracionário continua a referir-se àquele prefixo, não a uma seleção arbitrária por densidade.

TSP métrico e atalhos

Assume um grafo completo não dirigido, pesos não negativos e desigualdade triangular $c(u,w)\le c(u,v)+c(v,w)$. Constrói uma MST, duplica as suas arestas e percorre um circuito euleriano. Conserva a primeira visita a cada vértice e regressa ao início, usando ligações diretas para saltar visitas repetidas.

No quadrado de lado 1, fixa a MST $AB,BC,CD$ e o passeio $A,B,C,D,C,B,A$:

O passeio duplicado custa 6. A primeira visita dá a ordem $A,B,C,D$, e o circuito $A,B,C,D,A$ custa 4. O regresso $D,C,B,A$ foi substituído por $D,A$, custo 1 em vez de 3.

Retirar uma aresta de um circuito ótimo deixa uma árvore abrangente. Como os pesos são não negativos, $c(MST)\le OPT$. Duplicar dá custo $2c(MST)\le2OPT$. Cada atalho não aumenta o custo, pela desigualdade triangular aplicada repetidamente ao trecho removido. Assim o circuito final custa no máximo $2OPT$.

O custo exato depende da MST e da ordem de visita. No mesmo quadrado, a MST $AB,AD,DC$ pode produzir a ordem $A,B,D,C$; o circuito custa $2+2\sqrt2$, por atravessar as diagonais $BD$ e $CA$. Continua dentro da garantia. O algoritmo não promete encontrar o perímetro em qualquer desempate. Construir a MST domina o custo, por exemplo $O(n^2)$ com matriz; o passeio custa $O(n)$.

TSP geral

Sem a hipótese métrica, não há aproximação de fator constante $\rho\ge1$ em tempo polinomial, a menos que $P=NP$. Dado um grafo com $n$ vértices, completa-o atribuindo peso 1 às arestas existentes e $\rho n+1$ às restantes.

Se há ciclo hamiltoniano original, o ótimo novo é $n$, e a aproximação deve devolver custo no máximo $\rho n$. Se não há, qualquer circuito usa uma aresta nova e custa pelo menos $(\rho n+1)+(n-1)=\rho n+n$, acima daquele limiar. Comparar a saída com $\rho n$ decidiria HAM-CYCLE. A construção tem $O(n^2)$ arestas e custos de representação polinomial para $\rho$ fixo. São esses dois casos separados que tornam a redução útil.

Tornar os pesos métricos pode perder a razão

Num grafo completo não dirigido com pesos não negativos, seja $M$ o maior peso. Definir $c'(u,v)=c(u,v)+M$ para vértices distintos torna válidas as desigualdades triangulares: $c'(u,w)\le2M$, enquanto $c'(u,v)+c'(v,w)\ge2M$ para três vértices distintos. Mantém $c'(u,u)=0$.

Todos os circuitos hamiltonianos têm $n$ arestas. O seu custo aumenta exatamente $nM$, por isso a transformação conserva a ordem dos circuitos e o conjunto dos ótimos. Isso chega para transportar uma solução exata. Para uma aproximação de fator 2, a garantia nova apenas diz

$$C+nM\le2(OPT+nM).$$

Retirar a constante dá $C\le2OPT+nM$, não $C\le2OPT$. Se $M$ for grande relativamente ao ótimo original, o termo extra pode dominar. Preservar os ótimos não é suficiente para preservar uma razão de aproximação. Não há contradição com a impossibilidade de fator constante no TSP geral.

Cobertura de conjuntos

Dado um universo $U$ e uma família cuja união cobre $U$, queremos escolher o menor número de conjuntos que cubra todos os elementos. Cada conjunto tem custo 1. Em cada passo, o guloso escolhe o que contém mais elementos ainda por cobrir.

Com $U=\{1,2,3,4,5,6\}$, $S_1=\{1,2,3\}$, $S_2=\{4,5\}$, $S_3=\{6\}$ e $S_4=\{1,4\}$:

Escolha	Novos elementos	Elementos que faltam	Cobrança por novo elemento
$S_1$	1, 2, 3	4, 5, 6	$1/3$
$S_2$	4, 5	6	$1/2$
$S_3$	6	Nenhum	1

As cobranças somam $3(1/3)+2(1/2)+1=3$, o número de conjuntos escolhidos. Aqui, $S_1$ é obrigatório para cobrir 2 e 3, $S_2$ para cobrir 5 e $S_3$ para cobrir 6. Três é, portanto, ótimo nesta instância.

Em geral, seja $d\ge1$ o maior tamanho de um conjunto. Uma escolha com $r$ elementos novos cobra $1/r$ a cada um. Considera um conjunto $S$ de uma cobertura ótima: quando ainda faltam $k$ dos seus elementos, o guloso poderia escolher $S$, pelo que escolhe algum conjunto com pelo menos $k$ novos. A cobrança de cada elemento de $S$ retirado nesse passo é no máximo $1/k$.

Ordenando os elementos de $S$ pela altura em que são cobertos, a cobrança total fica limitada por

$$H_{|S|}=1+\frac12+\cdots+\frac1{|S|}\le H_d\le1+\ln d.$$

Somar sobre os conjuntos de uma cobertura ótima conta cada elemento pelo menos uma vez. Logo o custo guloso é no máximo $H_dOPT$. A garantia é logarítmica; ter encontrado um ótimo no exemplo não a transforma em otimalidade geral.

Uma implementação direta pode recalcular ganhos percorrendo todas as pertenças em cada passo. Se há $I$ pertenças e $q$ conjuntos, isso custa $O(|U|(I+q))$, um limite polinomial. Se faltam elementos e o maior ganho é zero, a família não cobre o universo e não existe solução. Para universo vazio, devolve a família vazia.