Soluções Inteligentes para Problemas Complexos
Coleção Escola de Lógica Matemática
JOÃO CARLOS MOREIRA
Doutor em Matemática
Universidade Federal de Uberlândia
Copyright©2013-2025 Coleção Escola de Lógica Matemática. Todos os direitos reservados.
Imagine que você precisa entregar encomendas em vinte endereços diferentes pela cidade, gastando o mínimo de combustível possível. Parece simples? Com apenas vinte pontos, existem mais de dois quintilhões de rotas possíveis para verificar. Mesmo o computador mais rápido do mundo levaria milhares de anos para encontrar a solução perfeita. Bem-vindo ao fascinante universo dos problemas computacionalmente difíceis, onde a busca pela perfeição se torna impossível e aprendemos a abraçar soluções "quase perfeitas" que funcionam magnificamente na prática.
Muitos problemas práticos do dia a dia escondem uma complexidade devastadora. Organizar horários escolares, roteirizar entregas, alocar recursos, cortar materiais minimizando desperdício — todos compartilham uma característica cruel: o número de soluções possíveis cresce exponencialmente com o tamanho do problema. Esta explosão combinatória transforma problemas aparentemente inocentes em desafios computacionais intratáveis.
Diante da impossibilidade prática de encontrar soluções ótimas, surge uma pergunta pragmática: precisamos mesmo da solução absolutamente perfeita? Na maioria dos casos reais, uma solução que seja 95% ou mesmo 90% ótima é perfeitamente aceitável e pode ser encontrada em fração de segundo. A aproximação algorítmica é a arte de trocar perfeição teórica por eficiência prática, mantendo garantias matemáticas sobre a qualidade das soluções.
A teoria da complexidade computacional classifica problemas segundo o tempo necessário para resolvê-los. Problemas em P têm soluções eficientes conhecidas. Problemas NP-completos e NP-difíceis provavelmente não têm algoritmos eficientes — a famosa questão P versus NP, com prêmio de um milhão de dólares, permanece em aberto. Esta classificação teórica tem consequências práticas profundas para o design de algoritmos.
Certos problemas aparecem repetidamente em contextos diversos, servindo como pedras fundamentais da teoria. O problema do caixeiro-viajante modela rotas de entrega. O problema da mochila representa alocação de recursos limitados. Coloração de grafos surge em alocação de frequências. Estes problemas paradigmáticos guiam o desenvolvimento de técnicas gerais de aproximação.
O campo da aproximação algorítmica nasceu nos anos 1960, quando pesquisadores perceberam que muitos problemas práticos importantes eram NP-difíceis. Pioneiros como Graham, Johnson e Christofides desenvolveram os primeiros algoritmos com garantias provadas. Nas décadas seguintes, técnicas sofisticadas emergiram, culminando no teorema PCP e na caracterização da aproximabilidade de problemas.
Aproximação algorítmica é sobre escolhas inteligentes. Trocamos garantia de otimalidade por velocidade. Aceitamos soluções ligeiramente piores em troca de certeza sobre sua qualidade. Preferimos algoritmos simples e robustos a métodos complexos e frágeis. Estes trade-offs não são concessões — são decisões estratégicas que tornam problemas intratáveis em ferramentas práticas.
Como quantificar o quão boa é uma solução aproximada? A razão de aproximação compara nossa solução com a ótima (desconhecida). Um algoritmo 2-aproximado garante soluções no máximo duas vezes piores que o ótimo. Análise competitiva compara algoritmos online com soluções offline. Análise suavizada considera perturbações aleatórias. Cada métrica captura aspectos diferentes da qualidade.
Algoritmos de aproximação operam silenciosamente em toda parte. Google Maps usa aproximações para calcular rotas rapidamente. Empresas de logística aproximam soluções de roteamento diariamente. Compiladores usam heurísticas para otimizar código. Redes sociais aproximam comunidades e influência. Machine learning é fundamentalmente sobre aproximar funções complexas. O mundo moderno funciona graças a aproximações inteligentes.
Aproximar não é desistir da excelência — é reconhecer limites fundamentais e trabalhar criativamente dentro deles. É a maturidade de aceitar que "muito bom" frequentemente é melhor que "perfeito mas impossível". É a sabedoria de que problemas reais demandam soluções reais, não idealizações matemáticas. A aproximação algorítmica encarna o espírito pragmático da computação moderna.
Nossa jornada explorará o rico universo da aproximação algorítmica. Começaremos entendendo a complexidade NP-difícil que motiva todo o campo. Estudaremos técnicas clássicas como algoritmos gulosos e programação linear. Exploraremos métodos avançados incluindo aproximação probabilística e meta-heurísticas. Veremos aplicações práticas em otimização, redes e aprendizado de máquina. Concluiremos vislumbrando fronteiras e direções futuras.
A aproximação algorítmica é onde teoria encontra prática, onde impossibilidade matemática se transforma em possibilidade engenhosa. É um campo vibrante que combina profundidade teórica com impacto prático imenso. Prepare-se para descobrir como abraçar a imperfeição pode ser o caminho para soluções verdadeiramente excelentes!
No coração da ciência da computação reside um mistério que vale literalmente um milhão de dólares: P é igual a NP? Esta questão aparentemente abstrata determina os limites fundamentais do que podemos computar eficientemente. Para entender por que precisamos de algoritmos de aproximação, devemos primeiro compreender a natureza dos problemas NP-difíceis — desafios computacionais tão complexos que provavelmente nunca teremos algoritmos rápidos para resolvê-los perfeitamente.
Dizemos que um algoritmo é eficiente quando seu tempo de execução cresce polinomialmente com o tamanho da entrada — O(n), O(n²), O(n³), etc. Algoritmos com tempo exponencial — O(2ⁿ), O(n!) — tornam-se rapidamente impraticáveis. Para n = 100, n² = 10.000 (manejável), mas 2¹⁰⁰ excede o número de partículas no universo. Esta diferença dramática separa o computável do meramente teórico.
A classe P contém problemas com algoritmos polinomiais conhecidos: ordenar números, encontrar caminhos mínimos, multiplicar matrizes. A classe NP contém problemas cujas soluções podem ser verificadas em tempo polinomial. Todo problema em P está em NP, mas o inverso permanece desconhecido. Se P = NP, criptografia moderna colapsa, mas ganharíamos poder computacional revolucionário.
Um problema é NP-completo quando todo problema em NP pode ser reduzido a ele em tempo polinomial. São os problemas mais difíceis em NP — resolver qualquer um eficientemente resolveria todos. Cook provou que SAT (satisfatibilidade booleana) é NP-completo. Milhares de problemas práticos foram posteriormente mostrados NP-completos através de cadeias de reduções.
Problemas NP-difíceis são ao menos tão difíceis quanto os NP-completos, mas não necessariamente em NP. Problemas de otimização são tipicamente NP-difíceis: encontrar a melhor solução é pelo menos tão difícil quanto decidir se existe solução boa. TSP de decisão ("existe rota de comprimento ≤ k?") é NP-completo; TSP de otimização ("qual a menor rota?") é NP-difícil.
Satisfatibilidade booleana (SAT) é o problema NP-completo arquetípico. Dada uma fórmula booleana, existe atribuição de valores verdadeiro/falso que a satisfaça? Sua universalidade vem da capacidade de codificar computação. Variantes como 3-SAT (cláusulas com exatamente 3 literais) permanecem NP-completas, fundamentando reduções para inúmeros outros problemas.
Grafos modelam redes, relações e estruturas, tornando problemas em grafos ubíquos. Muitos são NP-completos: encontrar clique máximo, coloração mínima, ciclo hamiltoniano, cobertura de vértices. Pequenas variações podem mudar drasticamente a complexidade: caminho mínimo é em P, mas caminho mais longo é NP-completo. Esta sensibilidade ilustra a sutileza da complexidade computacional.
Otimização combinatória busca a melhor solução entre finitas (mas exponencialmente muitas) possibilidades. O problema da mochila maximiza valor respeitando capacidade. Bin packing minimiza recipientes usados. Job scheduling minimiza tempo total. Estes problemas surgem constantemente em logística, manufatura e gestão de recursos, tornando sua intratabilidade particularmente frustrante.
Nem toda esperança está perdida para problemas NP-difíceis. Complexidade parametrizada identifica parâmetros que, quando pequenos, permitem algoritmos eficientes. Vertex cover é NP-completo, mas solucionável em O(2ᵏ·n) onde k é o tamanho da cobertura. Para k pequeno fixo, isso é polinomial em n. Esta abordagem oferece tratabilidade prática para instâncias com estrutura especial.
Décadas de esforço falharam em encontrar algoritmos polinomiais para problemas NP-completos. Milhares de problemas independentes, de áreas diversas, são todos equivalentemente difíceis. Hierarquias de complexidade colapsariam se P = NP. Resultados de circuit complexity sugerem separação. A comunidade acredita overwhelmingly que P ≠ NP, justificando investimento em aproximação.
Mesmo aproximação tem limites. Assumindo P ≠ NP, alguns problemas não admitem aproximação constante. Clique máximo não pode ser aproximado melhor que n¹⁻ᵋ para qualquer ε > 0. Coloração não pode ser aproximada dentro de n¹⁻ᵋ. Estes resultados de inaproximabilidade, provados via PCP theorem, mostram que aproximação não é panaceia universal.
A teoria da NP-completude não é apenas curiosidade acadêmica — é o fundamento que justifica todo o campo de aproximação algorítmica. Compreender que certos problemas são inerentemente intratáveis nos libera para buscar soluções práticas em vez de perseguir impossibilidades. A complexidade NP-difícil não é barreira, mas convite à criatividade: como podemos contornar limites fundamentais e ainda obter soluções úteis? Os próximos capítulos mostrarão exatamente como fazer isso!
Enfrentar problemas NP-difíceis requer arsenal diversificado de técnicas. Como guerreiros escolhendo armas para diferentes batalhas, devemos selecionar estratégias de aproximação adequadas a cada desafio. Algumas técnicas garantem soluções próximas do ótimo, outras são rápidas mas sem garantias fortes, algumas funcionam bem na prática apesar de péssimas garantias teóricas. Neste capítulo, exploraremos o rico conjunto de estratégias que tornam problemas intratáveis em ferramentas práticas.
Algoritmos gulosos tomam decisões localmente ótimas esperando alcançar um bom resultado global. Como alguém sempre pegando a maior moeda disponível para fazer troco, nem sempre chegam ao ótimo, mas frequentemente produzem soluções surpreendentemente boas. Sua simplicidade os torna rápidos, fáceis de implementar e analisar, ideais como primeira abordagem para novos problemas.
Muitos problemas combinatórios podem ser formulados como programas inteiros, difíceis de resolver. Relaxando restrições de integralidade, obtemos programas lineares solucionáveis eficientemente. A solução fracionária fornece limite inferior (ou superior) para o ótimo inteiro. Técnicas de arredondamento convertem soluções fracionárias em inteiras, mantendo garantias de qualidade.
Programação dinâmica resolve problemas quebrando-os em subproblemas sobrepostos. Para problemas NP-difíceis, o número de subproblemas pode ser exponencial. Aproximação via DP agrupa estados similares, reduzindo o espaço de estados. Técnicas incluem discretização, scaling e trimming. O resultado são algoritmos pseudo-polinomiais ou esquemas de aproximação.
Aleatoriedade é surpreendentemente poderosa para aproximação. Algoritmos randomizados fazem escolhas aleatórias durante execução, garantindo boa performance esperada. Monte Carlo pode errar mas roda em tempo fixo. Las Vegas sempre acerta mas tempo é variável. Técnicas incluem amostragem, hashing, random rounding e método probabilístico.
Começando com solução inicial, busca local explora vizinhança procurando melhorias. Como escalar montanha na neblina, move-se sempre para cima até não haver direção melhor. Variantes incluem simulated annealing (aceita pioras probabilisticamente), tabu search (memória previne ciclos) e variable neighborhood search (muda estrutura de vizinhança). Sem garantias teóricas fortes, mas excelentes na prática.
Inspirados em programação linear, algoritmos primais-duais mantêm soluções viáveis para versões primal e dual do problema simultaneamente. A diferença entre valores objetivo primal e dual limita a distância do ótimo. Aumentam soluções incrementalmente, mantendo complementaridade. Produzem não apenas soluções aproximadas mas também certificados de qualidade.
Problemas grandes frequentemente têm estrutura decomponível. Particionamento divide problema em subproblemas menores, resolve independentemente e combina soluções. Hierarquia explora estrutura multi-nível. Separadores em grafos permitem divisão equilibrada. Perda na recombinação é controlada, garantindo aproximação global.
Pré-processamento pode dramaticamente simplificar instâncias antes de aplicar aproximação. Kernelização reduz a instância preservando solução. Eliminação de dominados remove opções claramente inferiores. Fixação de variáveis usa argumentos de otimalidade local. Crown decomposition particiona vértices estruturalmente. Instância reduzida permite algoritmos mais sofisticados.
Combinar múltiplas estratégias frequentemente supera abordagens puras. Meta-heurísticas como algoritmos genéticos combinam busca local com população. Matheuristics integram programação matemática com heurísticas. Hiperheurísticas selecionam heurísticas dinamicamente. Portfolio algorithms executam múltiplos algoritmos em paralelo. Hibridização explora forças complementares de diferentes técnicas.
Problemas online requerem decisões sem conhecimento futuro. Como investir sem saber preços futuros, devemos decidir irrevogavelmente baseados em informação parcial. Análise competitiva compara com ótimo offline onisciente. Estratégias incluem algoritmos de reserva, randomização para quebrar determinismo adversarial, e aprendizado de padrões históricos.
Este arsenal de estratégias transforma problemas NP-difíceis de muralhas intransponíveis em desafios manejáveis. Cada técnica tem seus pontos fortes, limitações e domínios de aplicação ideais. O verdadeiro mestre em aproximação não se casa com uma única abordagem, mas escolhe e combina estratégias conforme a natureza do problema. Com estas ferramentas, estamos prontos para explorar como garantir e analisar a qualidade de nossas aproximações!
Aproximar sem garantias é como navegar sem bússola — podemos chegar a algum lugar, mas não sabemos quão longe estamos do destino. A beleza da aproximação algorítmica está em fornecer garantias matemáticas rigorosas sobre a qualidade das soluções, mesmo sem conhecer o ótimo. Neste capítulo, exploraremos como analisar, provar e garantir que nossas aproximações estão próximas o suficiente da perfeição para serem úteis na prática.
A razão de aproximação é a métrica fundamental de qualidade. Para problemas de minimização, um algoritmo é α-aproximado se sempre produz solução de custo no máximo α vezes o ótimo. Para maximização, garante valor pelo menos OPT/α. Um algoritmo 2-aproximado garante solução no máximo duas vezes pior que a perfeita — reconfortante quando perfeição é inatingível.
Garantias de aproximação são tipicamente para pior caso — valem para qualquer instância possível. Como seguro que cobre todos os acidentes, não apenas os prováveis. Isso torna análises pessimistas: algoritmos frequentemente performam muito melhor na prática. Mas garantia de pior caso oferece certeza absoluta, valiosa em aplicações críticas.
PTAS (Polynomial-Time Approximation Scheme) é família de algoritmos que, para qualquer ε > 0, encontra solução (1+ε)-aproximada. Usuário escolhe precisão desejada: ε = 0.1 para 10% de erro, ε = 0.01 para 1%. FPTAS (Fully PTAS) roda em tempo polinomial também em 1/ε. EPTAS (Efficient PTAS) tem dependência ainda melhor. Estes esquemas oferecem trade-off explícito entre tempo e qualidade.
Nem todo problema admite boa aproximação. Assumindo P≠NP, existem limites fundamentais. Clique não pode ser aproximado melhor que n¹⁻ᵋ. Set cover não admite aproximação melhor que ln n. Estes limites, provados via reduções gap-preserving e PCP theorem, mostram que alguns problemas são inerentemente difíceis de aproximar.
Para algoritmos randomizados, analisamos performance esperada. Um algoritmo tem aproximação esperada α se E[ALG]/OPT ≤ α. Concentração mostra que resultado está próximo da esperança com alta probabilidade. Desrandomização converte algoritmos randomizados em determinísticos preservando garantias. Method of conditional expectations é técnica poderosa para isso.
Para algoritmos online, análise competitiva compara com ótimo offline. Um algoritmo é c-competitivo se seu custo é no máximo c vezes o ótimo que conhece o futuro. Análise amortizada considera sequências de operações, permitindo que operações caras sejam compensadas por baratas. Resource augmentation permite ao online recursos extras, tornando comparação mais justa.
Entre pior caso pessimista e caso médio otimista, análise suavizada considera instâncias levemente perturbadas. Se algoritmo é eficiente para qualquer instância após pequena perturbação aleatória, tem complexidade suavizada polinomial. Explica por que simplex funciona bem na prática apesar de exponencial no pior caso. Captura robustez a ruído, comum em dados reais.
Muitas instâncias práticas têm estrutura especial que permite melhor aproximação. Grafos planares, euclidianos ou com treewidth limitado admitem PTAS para muitos problemas. Instâncias com grande gap de integralidade são fáceis para LP-rounding. Identificar e explorar estrutura especial melhora dramaticamente garantias práticas.
Boas aproximações vêm com certificados verificáveis de qualidade. Solução dual viável fornece limite inferior para minimização. Relaxação fracionária limita ótimo inteiro. Estes certificados não apenas provam qualidade mas guiam melhoramento. Se gap entre primal e dual é pequeno, sabemos estar próximos do ótimo mesmo sem conhecê-lo.
Problemas reais frequentemente têm múltiplos objetivos conflitantes. Aproximação bi-critério relaxa múltiplas dimensões simultaneamente. Pareto-aproximação encontra soluções próximas da fronteira Pareto-ótima. Podemos trocar qualidade em um objetivo por outro, oferecendo flexibilidade valiosa. Análise multi-objetivo captura melhor necessidades práticas.
Garantias de qualidade transformam aproximação de arte em ciência. Elas nos dizem não apenas que nossas soluções são boas, mas exatamente quão boas são, no pior caso ou em média, deterministicamente ou com alta probabilidade. Com este arsenal analítico, podemos escolher algoritmos com confiança, comunicar limitações honestamente, e dormir tranquilos sabendo que nossas aproximações têm fundamento matemático sólido. Agora exploraremos uma das técnicas mais simples e poderosas: algoritmos gulosos!
Na fábula de Esopo, a formiga trabalhadora junta grãos um por vez, sempre escolhendo o mais próximo. Esta estratégia simples — fazer a escolha localmente ótima a cada passo — é a essência dos algoritmos gulosos. Surpreendentemente, esta abordagem míope frequentemente produz soluções excelentes para problemas complexos. Como a formiga que constrói grandes reservas com decisões simples, algoritmos gulosos transformam problemas NP-difíceis em soluções práticas através de escolhas locais inteligentes.
Algoritmos gulosos nunca reconsideram decisões passadas. Como um alpinista sempre subindo a encosta mais íngreme, podem não alcançar o pico mais alto, mas certamente chegarão a algum pico. Esta irrevogabilidade torna-os rápidos e simples, mas também limita seu poder. O desafio está em identificar quando escolhas locais levam a boas soluções globais.
No problema de set cover, queremos cobrir elementos com o menor número de conjuntos. O algoritmo guloso repetidamente escolhe o conjunto cobrindo mais elementos descobertos. Simples e intuitivo, garante aproximação O(ln n), e este limite é apertado — nenhum algoritmo polinomial faz substancialmente melhor assumindo P≠NP. Um triunfo de simplicidade com garantia quase ótima.
Escalonamento é terreno fértil para algoritmos gulosos. Para minimizar makespan em máquinas paralelas, List Scheduling aloca cada job à máquina menos carregada. Garante 2-aproximação, melhorando para 4/3 com jobs ordenados (LPT - Longest Processing Time). Para minimizar atraso ponderado, ordenar por razão peso/tempo é ótimo. Diferentes objetivos requerem diferentes critérios gulosos.
Nem todo guloso aproxima — alguns encontram o ótimo! Kruskal constrói árvore geradora mínima adicionando arestas em ordem crescente de peso, pulando as que criariam ciclos. A propriedade de matroide garante otimalidade. Este exemplo mostra que estrutura correta torna estratégia gulosa perfeita, não apenas boa.
Para mochila fracionária, ordenar por valor/peso e pegar gananciosamente é ótimo. Para mochila 0/1, mesma estratégia pode ser arbitrariamente ruim. Mas modificação simples — comparar solução gulosa com item mais valioso sozinho — garante 2-aproximação. Pequenos ajustes podem dramaticamente melhorar garantias gulosas.
First-fit coloring atribui a cada vértice a menor cor não usada por vizinhos. Para grafos gerais, pode usar Δ+1 cores onde Δ é grau máximo. Ordenações inteligentes melhoram performance: DSatur (grau de saturação), largest-first, random. Para grafos bipartidos, guloso encontra 2-coloração ótima. Estrutura específica melhora dramaticamente resultado guloso.
Funções submodulares têm retornos decrescentes — adicionar elemento a conjunto pequeno vale mais que a conjunto grande. Muitos objetivos práticos são submodulares: cobertura, influência, informação. Algoritmo guloso que maximiza ganho marginal garante (1-1/e)-aproximação ≈ 0.63. Esta garantia universal para classe ampla de funções demonstra poder de propriedades estruturais.
Provar garantias para algoritmos gulosos requer técnicas específicas. Exchange argument mostra que trocar elementos não melhora solução. Charging argument cobra custo do guloso no ótimo. Potential function tracked progresso monotônico. Dual fitting mostra que guloso implicitamente constrói boa solução dual. Cada técnica ilumina por que simplicidade funciona.
Gulosos podem falhar espetacularmente. Para TSP, nearest neighbor pode produzir tour Ω(log n) vezes ótimo. Para mochila 0/1, ganância por eficiência pode desperdiçar quase toda capacidade. Identificar quando guloso falha é tão importante quanto saber quando funciona. Contraexemplos educam sobre necessidade de técnicas mais sofisticadas.
Adicionar aleatoriedade melhora algoritmos gulosos. Em vez de sempre escolher o melhor, selecionar aleatoriamente entre bons candidatos. GRASP (Greedy Randomized Adaptive Search) constrói soluções gulosas randomizadas, depois melhora com busca local. Randomização quebra simetrias e escapa de armadilhas determinísticas.
Algoritmos gulosos encarnam o princípio de que simplicidade tem valor intrínseco. Fáceis de entender, implementar e analisar, frequentemente produzem soluções surpreendentemente boas. Quando funcionam, são imbatíveis em elegância. Quando falham, apontam necessidade de técnicas mais sofisticadas. Como ferramentas versáteis numa caixa, gulosos devem ser sempre a primeira tentativa — rápidos de testar e, com sorte, suficientes. Quando não são, pelo menos fornecem baseline e intuição para abordagens mais complexas que exploraremos a seguir!
Imagine tentar encaixar caixas quadradas em um caminhão, mas com uma reviravolta: você pode temporariamente torná-las líquidas, otimizar o líquido, e depois solidificá-las novamente. Esta é a essência da relaxação em programação linear — transformamos problemas discretos difíceis em contínuos tratáveis, resolvemos eficientemente, e convertemos de volta para o discreto. Esta técnica poderosa une a elegância da otimização contínua com as necessidades práticas de decisões discretas.
Muitos problemas combinatórios naturalmente se expressam como programas inteiros. Variáveis binárias representam decisões sim/não. Restrições lineares capturam relações e limitações. O objetivo linear mede qualidade. Mas resolver programas inteiros é NP-difícil. A mágica está em relaxar integralidade: permitir variáveis fracionárias transforma problema intratável em linear, solucionável em tempo polinomial.
Programas lineares são solucionáveis eficientemente via simplex (exponencial no pior caso mas rápido na prática) ou métodos de ponto interior (polinomiais garantidos). Para LPs especiais, algoritmos combinatórios são ainda mais rápidos. A solução ótima fornece não apenas valores das variáveis mas também informação dual — preços sombra que medem sensibilidade a restrições.
Converter solução fracionária em inteira preservando qualidade é arte delicada. Arredondamento determinístico usa thresholds: x ≥ 0.5 vira 1. Arredondamento randomizado interpreta frações como probabilidades. Clustering agrupa variáveis relacionadas. Iterative rounding fixa variáveis com valores extremos. Cada técnica tem domínios onde brilha.
Vertex cover exemplifica beleza de LP-relaxação. Formulação: min Σx_v sujeito a x_u + x_v ≥ 1 para cada aresta. Relaxação permite valores fracionários. Arredondamento simples: incluir vértices com x_v ≥ 0.5. Garante 2-aproximação pois cada aresta tem peso total ≥ 1, então algum endpoint tem peso ≥ 0.5. Elegância em ação.
Problema de localização de instalações: abrir facilities para servir clientes minimizando custos de abertura e conexão. LP-relaxação com arredondamento sofisticado garante aproximação constante. Técnica de filtering reduz dependências. Análise dual mostra que arredondamento implicitamente constrói boa solução dual, provando qualidade.
SDP generaliza LP permitindo matrizes de variáveis com restrição de semidefinição positiva. Mais poderoso que LP, ainda solucionável eficientemente. Para Max-Cut, SDP relaxação de Goemans-Williamson com arredondamento hiperplano aleatório garante 0.878-aproximação, melhor possível assumindo Unique Games Conjecture. Fronteira da aproximação moderna.
Todo LP tem dual associado. Teorema forte da dualidade: ótimos primal e dual são iguais (quando existem). Solução dual fornece certificado de otimalidade para primal. Para aproximação, dual viável dá lower bound, limitando distância do ótimo. Algoritmos primal-dual exploram esta relação, construindo soluções primal e dual simultaneamente.
Algoritmos primal-dual mantêm soluções primal e dual, melhorando ambas iterativamente. Começam com dual viável (talvez trivial) e primal inviável. Aumentam dual até que eventos primal ocorram. Usam folgas complementares para guiar construção. Produzem não apenas solução aproximada mas certificado de qualidade. Unificam muitos algoritmos clássicos.
Hierarquias sistemáticas fortalecem relaxações adicionando restrições válidas. Lovász-Schrijver, Sherali-Adams e Lasserre criam sequências de relaxações convergindo ao hull inteiro. Cada nível é mais forte mas mais caro. Para alguns problemas, poucos níveis bastam para ótimo. Para outros, precisamos níveis exponenciais. Trade-off fundamental entre força e complexidade.
Para LPs com muitas variáveis, column generation trabalha com subconjunto, adicionando colunas conforme necessário. Resolvemos LP mestre restrito, usamos dual para identificar colunas melhoradoras via pricing subproblem. Iteramos até otimalidade. Efetivo para problemas de roteamento, scheduling, cutting stock. Combina decomposição com geração dinâmica.
Programação linear e relaxação formam ponte elegante entre o discreto e o contínuo. Como alquimistas modernos, transformamos problemas inteiros duros em lineares suaves, otimizamos no reino contínuo, e cristalizamos de volta ao discreto. Esta dança entre mundos produz algumas das melhores aproximações conhecidas, com garantias rigorosas e certificados verificáveis. A beleza está em como estrutura geométrica do poliedro relaxado guia nossa busca no espaço discreto. Com estas ferramentas poderosas, estamos prontos para explorar outra fonte de poder: a aleatoriedade!
Jogar moedas para tomar decisões computacionais parece contraintuitivo — afinal, queremos certeza, não apostas. Mas a aleatoriedade é surpreendentemente poderosa na aproximação algorítmica. Como um jogador de poker que vence não por ter sempre as melhores cartas, mas por jogar probabilidades sabiamente, algoritmos randomizados alcançam excelente performance esperada com elegância impressionante. Neste capítulo, descobriremos como o acaso controlado produz soluções deterministicamente boas.
Aleatoriedade oferece vantagens únicas: simplicidade algorítmica, análise limpa via esperança, robustez contra adversários, paralelização natural. Paradoxalmente, adicionar incerteza pode produzir mais certeza — a lei dos grandes números garante concentração em torno da média. Randomização não é desistir de controle, mas abraçar ferramental matemático poderoso.
Para particionar vértices maximizando arestas cortadas, algoritmo ultra-simples: colocar cada vértice aleatoriamente em um lado. Esperança: metade das arestas cortadas. Como ótimo corta no máximo todas arestas, temos 0.5-aproximação esperada! Derandomização via método das esperanças condicionais produz algoritmo determinístico com mesma garantia. Simplicidade extrema com garantia respeitável.
Interpretando solução fracionária de LP como probabilidades, randomized rounding preserva esperança enquanto produz solução inteira. Para set cover, incluir conjunto S com probabilidade proporcional a x_S garante cobertura com alta probabilidade após amplificação logarítmica. Combina poder de LP com flexibilidade probabilística.
Técnica não-algorítmica mas fundamental: provar existência mostrando que objeto aleatório tem propriedade desejada com probabilidade positiva. Se esperança é boa, deve existir realização ao menos tão boa. Transforma argumentos existenciais em algoritmos via derandomização. Ferramenta poderosa para garantir aproximabilidade.
Monte Carlo roda em tempo fixo mas pode errar com pequena probabilidade. Para aproximação, erro significa qualidade pior que garantida. Repetição independente reduz probabilidade de falha exponencialmente. Para decisão, one-sided error (sempre correto quando diz "não") é particularmente útil. Trade-off explícito entre tempo e confiabilidade.
Las Vegas sempre produz resposta correta mas tempo é variável aleatório. Para aproximação, sempre garante qualidade prometida, mas tempo para encontrá-la varia. Randomized quicksort é exemplo clássico. Conversão entre Monte Carlo e Las Vegas possível com overhead. Preferível quando correção é crítica mas tempo flexível.
Hashing universal mapeia universo grande para range pequeno preservando propriedades probabilisticamente. Sketching comprime dados mantendo informação aproximada. Count-min sketch estima frequências. MinHash aproxima similaridade Jaccard. Bloom filters testam pertinência com falsos positivos controlados. Compressão massiva com garantias probabilísticas.
Inspirado em metalurgia, simulated annealing escapa de ótimos locais aceitando pioras probabilisticamente. Temperatura alta inicial permite exploração ampla. Resfriamento gradual foca em refinamento. Probabilidade de aceitar piora decresce com temperatura e magnitude da piora. Convergência teórica para ótimo global com resfriamento suficientemente lento (impraticável). Na prática, produz excelentes soluções.
Desigualdades de concentração quantificam quão próxima variável aleatória está de sua esperança. Markov, Chebyshev, Chernoff, Hoeffding, Azuma fornecem bounds progressivamente mais fortes sob condições mais restritivas. Essenciais para analisar algoritmos randomizados, garantindo que performance típica está próxima da esperada. Transformam análise de caso médio em garantias de alta probabilidade.
Converter algoritmo randomizado em determinístico preservando garantias. Método das esperanças condicionais fixa variáveis mantendo esperança boa. Pessimistic estimators calculam esperança eficientemente. PRGs (pseudo-random generators) com seed pequeno enumeram sobre seeds. Expanders substituem aleatoriedade completa por grafos com propriedades pseudo-aleatórias.
Métodos probabilísticos revelam que abraçar a incerteza paradoxalmente produz certeza. Como dados que sempre caem com média previsível apesar de cada lançamento ser imprevisível, algoritmos randomizados alcançam garantias sólidas através do acaso controlado. A elegância está em como ferramentas probabilísticas simplificam design e análise, produzindo algoritmos que seriam complexos ou impossíveis deterministicamente. Com probabilidade no nosso arsenal, estamos prontos para explorar técnicas que abandonam garantias teóricas em favor de performance prática: heurísticas e meta-heurísticas!
Enquanto algoritmos com garantias matemáticas são como engenheiros calculando precisamente cada viga de uma ponte, heurísticas são como artesãos experientes que "sentem" a solução correta. Sem promessas formais de qualidade, estas técnicas conquistaram a prática através de performance consistentemente excelente em problemas reais. Meta-heurísticas vão além, fornecendo frameworks gerais para navegar espaços de solução complexos. Neste capítulo, exploraremos este mundo onde intuição, experiência e criatividade superam provas rigorosas.
Heurísticas abraçam pragmatismo sobre purismo. Reconhecem que instâncias práticas frequentemente têm estrutura não capturada por análise de pior caso. Priorizam simplicidade, velocidade e performance típica sobre garantias universais. Como regras práticas que funcionam 99% do tempo, trocam certeza matemática por eficácia empírica. Esta filosofia libertadora permite explorar técnicas poderosas além do alcance da análise formal.
Inspirados na evolução biológica, algoritmos genéticos mantêm população de soluções que evoluem através de seleção, crossover e mutação. Soluções melhores têm maior probabilidade de reproduzir. Crossover combina características de pais bem-sucedidos. Mutação introduz diversidade. Após gerações, população converge para soluções de alta qualidade. Metáfora biológica guia exploração efetiva do espaço de soluções.
Busca tabu adiciona memória à busca local, proibindo movimentos recentes para evitar ciclos. Lista tabu registra atributos de soluções ou movimentos recentes. Aspiração permite violar tabu se movimento é excepcional. Intensificação foca em regiões promissoras. Diversificação força exploração de novas áreas. Memória transforma busca local míope em exploração estratégica.
ACO (Ant Colony Optimization) simula formigas depositando feromônio em caminhos. Formigas probabilisticamente seguem trilhas com mais feromônio. Bons caminhos recebem reforço. Evaporação previne convergência prematura. Emerge comportamento coletivo inteligente de agentes simples. Particularmente efetivo para problemas de roteamento e sequenciamento.
PSO modela enxame de partículas explorando espaço de soluções. Cada partícula tem posição (solução) e velocidade. Atualização combina: inércia (continuar direção), atração ao melhor pessoal (memória individual), atração ao melhor global (conhecimento social). Simplicidade conceitual com apenas alguns parâmetros. Efetivo para otimização contínua e problemas com muitos ótimos locais.
VNS sistematicamente muda estrutura de vizinhança durante busca. Quando preso em ótimo local em uma vizinhança, muda para outra onde pode haver melhoria. Combina perturbação (shaking) para escapar com busca local para refinamento. Explora fato de que ótimo local em uma estrutura pode não ser em outra. Framework flexível adaptável a muitos problemas.
Greedy Randomized Adaptive Search Procedure combina construção gulosa randomizada com busca local. Construção usa lista restrita de candidatos (RCL) dos melhores elementos, escolhendo aleatoriamente. Randomização produz soluções iniciais diversas. Busca local melhora cada solução. Multi-start nature escapa de ótimos locais. Simples mas poderoso, amplamente aplicável.
ILS aplica perturbações a ótimos locais para escapar e continuar busca. Perturbação deve ser forte o suficiente para escapar da bacia de atração, mas não tão forte que destrua estrutura boa. Critério de aceitação decide se continuar de nova solução ou retornar à anterior. Histórico pode guiar intensidade de perturbação. Framework simples mas efetivo para muitos problemas.
Hiperheurísticas são "heurísticas para escolher heurísticas". Em vez de operar diretamente em soluções, selecionam qual heurística de baixo nível aplicar. Aprendem quais heurísticas funcionam bem em diferentes estágios ou tipos de instância. Generalizam através de problemas. Adaptam-se automaticamente sem conhecimento específico do domínio. Promessa de solucionadores mais gerais e robustos.
Matheuristics combinam programação matemática com heurísticas, explorando sinergias. Decomposição fixa variáveis heuristicamente, resolve subproblema exato. Local branching adiciona restrições limitando distância de solução incumbente. Relaxation induced neighborhoods exploram vizinhanças definidas por relaxação. Corridor method restringe espaço baseado em soluções promissoras. União de rigor matemático com flexibilidade heurística.
Sem garantias teóricas, validação empírica rigorosa é crucial. Benchmarks padronizados permitem comparação justa. Análise estatística distingue ruído de melhoria real. Perfis de performance mostram robustez através de instâncias. Ablation study identifica componentes críticos. Reprodutibilidade requer documentação detalhada de parâmetros e ambiente.
Heurísticas e meta-heurísticas representam o triunfo do pragmatismo na otimização. Liberadas das amarras de garantias teóricas, exploram livremente metáforas naturais, intuições práticas e criatividade algorítmica. Como artistas que criam beleza sem fórmulas, estas técnicas produzem soluções impressionantes através de mecanismos que desafiam análise formal. Seu sucesso prático massivo valida a sabedoria de que, às vezes, fazer funcionar bem é mais importante que provar que funciona. Com este arsenal prático, vamos ver como todas estas técnicas se aplicam a problemas reais!
Toda teoria elegante do mundo não vale nada se não resolver problemas reais. Felizmente, aproximação algorítmica não é apenas exercício intelectual — é o motor invisível que faz o mundo moderno funcionar. De rotas de entrega a redes sociais, de alocação de recursos a aprendizado de máquina, algoritmos de aproximação resolvem diariamente problemas que afetam bilhões. Neste capítulo, veremos como as técnicas que estudamos se materializam em aplicações que você provavelmente usou hoje.
Empresas de entrega enfrentam diariamente o problema do caixeiro-viajante em escala massiva. Amazon roteiriza milhões de pacotes, FedEx otimiza rotas aéreas e terrestres, Uber conecta motoristas a passageiros. Algoritmos de aproximação tornam tratável o que seria impossível resolver otimamente. Savings algorithm, sweep algorithm, e meta-heurísticas como busca tabu produzem rotas eficientes em segundos para milhares de pontos.
Projetar redes de comunicação eficientes envolve múltiplos problemas NP-difíceis: posicionamento de torres, alocação de frequências, roteamento de tráfego. Aproximações garantem conectividade confiável e throughput alto sem explodir custos. Algoritmos para Steiner tree minimizam cabeamento. Graph coloring aloca frequências evitando interferência. Load balancing distribui tráfego evitando congestionamento.
Datacenters executam milhões de tarefas em milhares de servidores. Escalonamento eficiente é crucial para performance e custo. Bin packing algorithms alocam VMs minimizando servidores ativos. Load balancing distribui requisições uniformemente. Energy-aware scheduling reduz consumo. Aproximações online lidam com chegada dinâmica de jobs sem conhecimento futuro.
Aprendizado de máquina é fundamentalmente sobre aproximação — aproximar funções complexas com modelos tratáveis. Feature selection é um problema de cobertura. Clustering é particionamento de grafos. Training de redes neurais usa SGD, uma aproximação estocástica. Pruning e quantização aproximam modelos grandes com menores. Todo pipeline ML está permeado de aproximações inteligentes.
Analisar dados biológicos massivos requer aproximações espertas. Alinhamento de sequências usa programação dinâmica aproximada. Phylogenetic tree construction é Steiner tree em espaço de sequências. Protein folding prediction usa simulated annealing e algoritmos genéticos. Gene regulatory network inference combina clustering com aprendizado de grafos. Vida é complexa demais para soluções exatas.
Mercados financeiros demandam decisões rápidas sobre problemas complexos. Portfolio optimization é quadratic programming em alta dimensão. Option pricing usa Monte Carlo. Risk management emprega aproximações de Value at Risk. High-frequency trading requer algoritmos online ultrarrápidos. Aproximações balanceiam precisão com velocidade crucial em mercados voláteis.
Bilhões de usuários geram grafos massivos demandando análise eficiente. Influence maximization para marketing viral usa greedy submodular. Community detection emprega spectral clustering aproximado. Recommendation systems combinam collaborative filtering com aproximações de matriz. Link prediction usa embeddings aproximados. Escala força aproximação em cada componente.
Cidades inteligentes otimizam recursos urbanos usando aproximação. Traffic light synchronization minimiza congestionamento. Waste collection routing reduz combustível. Emergency service placement maximiza cobertura. Public transport scheduling balanceia serviço e custo. Smart grid management equilibra oferta e demanda. Cada sistema usa aproximações para decisões em tempo real.
Jogos modernos resolvem problemas complexos em tempo real. Pathfinding usa A* com heurísticas admissíveis. Procedural generation emprega noise functions e L-systems aproximados. AI de jogos usa Monte Carlo tree search com UCT. Matchmaking balanceia skill aproximando ratings. Physics simulation aproxima mecânica real para performance. Diversão depende de aproximações rápidas e convincentes.
Fábricas modernas são sinfonias de otimização aproximada. Production scheduling minimiza makespan e atrasos. Cutting stock problems reduzem desperdício de material. Assembly line balancing equaliza workload. Supply chain optimization coordena fornecedores e demanda. Quality control usa statistical process control aproximado. Eficiência industrial depende de aproximações práticas.
Estas aplicações demonstram que aproximação algorítmica não é concessão, mas necessidade. O mundo real é complexo demais, dinâmico demais, grande demais para soluções perfeitas. Aproximações inteligentes tornam o intratável em prático, o impossível em rotineiro. Cada vez que você recebe uma encomenda, usa GPS, assiste streaming, ou joga online, algoritmos de aproximação trabalham silenciosamente nos bastidores. São os heróis desconhecidos da era digital, transformando problemas NP-difíceis em conveniências cotidianas!
Como exploradores no limite do mapa conhecido, pesquisadores em aproximação algorítmica constantemente expandem fronteiras do possível. Computação quântica promete revolucionar o que consideramos tratável. Aprendizado de máquina está transformando como projetamos algoritmos. Novos modelos computacionais desafiam paradigmas estabelecidos. Neste capítulo final, vislumbraremos o futuro da aproximação, onde os desafios de hoje se tornarão as ferramentas de amanhã.
Algoritmos quânticos prometem speedups dramáticos para certos problemas. Grover's algorithm oferece busca quadrática mais rápida. QAOA (Quantum Approximate Optimization Algorithm) ataca problemas combinatórios. VQE aproxima estados fundamentais. Mas computadores quânticos são ruidosos e limitados. Ironicamente, aproximação é crucial: algoritmos quânticos aproximados são mais robustos a erros que exatos. O futuro pode ser aproximação quântica de problemas clássicos difíceis.
Machine learning está revolucionando design algorítmico. Learned indexes substituem estruturas de dados tradicionais. Neural combinatorial optimization treina redes para resolver TSP. Learning-augmented algorithms melhoram garantias usando predições. AutoML-Zero evolui algoritmos do zero. Reinforcement learning descobre heurísticas superiores. O futuro pode ser algoritmos que aprendem a aproximar, adaptando-se a distribuições específicas de instâncias.
MapReduce, Spark e frameworks similares mudaram computação em larga escala. Mas paralelizar aproximações é sutil. Novos modelos como MPC (Massively Parallel Computation) formalizam trade-offs entre rounds de comunicação e aproximação. Algoritmos round-efficient sacrificam qualidade por menos sincronização. Distributed approximation lida com dados particionados. O futuro é aproximação consciente de arquitetura paralela.
Dados chegam continuamente, decisões são irrevogáveis, memória é limitada. Streaming algorithms processam dados uma vez com espaço sublinear. Competitive analysis compara com ótimo offline. Prophet inequalities limitam preço da incerteza. Online convex optimization aprende enquanto decide. O futuro é aproximação que funciona sob restrições severas de recursos e informação.
Algoritmos impactam vidas, levantando questões éticas. Fairness constraints tornam otimização mais difícil. Individual fairness requer tratar similares similarmente. Group fairness equaliza outcomes entre grupos. Price of fairness quantifica custo de equidade. Approximation-preserving reductions mantêm garantias e fairness. O futuro exige algoritmos que aproximam bem enquanto são justos.
Mudança climática demanda otimização de recursos planetários. Smart grids balanceiam energia renovável variável. Conservation planning protege biodiversidade com orçamento limitado. Carbon-aware computing minimiza emissões. Circular economy optimization reduz desperdício. Aproximação é essencial: problemas são massivos, multi-objetivo, e urgentes. O futuro é aproximação para sustentabilidade global.
Conforme algoritmos tomam decisões críticas, verificar aproximações torna-se vital. Certified approximation fornece garantias verificáveis. Proof-carrying code inclui provas de correção. Differential privacy garante privacidade com utilidade aproximada. Byzantine-robust approximation resiste a participantes maliciosos. O futuro exige aproximações que podemos confiar em contextos adversariais.
Fine-grained complexity estuda problemas em P, distinguindo n² de n^2.5. Parameterized approximation combina FPT com aproximação. Average-case complexity analisa instâncias típicas. Smoothed analysis interpola pior e médio caso. Communication complexity limita aproximação distribuída. O futuro da teoria é nuançado, indo além de dicotomias simples.
AGI enfrentará problemas computacionalmente intratáveis constantemente. Aproximação será essencial para inteligência prática. Meta-reasoning sobre quando aproximar. Transfer learning de estratégias de aproximação. Compositional approximation para problemas complexos. O futuro pode ser AGI que raciocina sobre trade-offs de aproximação como humanos fazem intuitivamente.
Conforme problemas crescem em escala e complexidade, aproximação torna-se não opcional, mas essencial. Computadores quânticos aproximarão. IAs aproximarão. Sistemas distribuídos aproximarão. A questão não é se aproximar, mas como aproximar inteligentemente. O futuro pertence a quem dominar a arte de trocar perfeição inatingível por excelência alcançável.
A jornada da aproximação algorítmica está apenas começando. Dos primeiros algoritmos gulosos aos futuros solucionadores quânticos, o princípio permanece: perfeição é luxo que raramente podemos pagar, mas excelência aproximada está ao nosso alcance. As fronteiras que exploramos hoje — quantum, ML, fairness, sustentabilidade — serão os fundamentos de amanhã. O futuro será construído não por aqueles que buscam soluções perfeitas impossíveis, mas por aqueles que dominam a arte sublime da aproximação inteligente. Neste mundo de complexidade crescente, aproximação não é compromisso — é sabedoria!
Este volume sobre Aproximação Algorítmica foi construído sobre décadas de pesquisa em ciência da computação teórica e aplicada. As referências abrangem desde trabalhos fundamentais estabelecendo a teoria da NP-completude até desenvolvimentos recentes em aprendizado de máquina e computação quântica. Esta bibliografia oferece recursos para aprofundamento em cada aspecto da aproximação algorítmica, desde fundamentos teóricos até aplicações práticas em problemas do mundo real.
AGARWAL, Pankaj K.; HAR-PELED, Sariel; VARADARAJAN, Kasturi R. Geometric Approximation via Coresets. Combinatorial and Computational Geometry, v. 52, p. 1-30, 2005.
ALON, Noga; SPENCER, Joel H. The Probabilistic Method. 4th ed. Hoboken: John Wiley & Sons, 2016.
ARORA, Sanjeev; BARAK, Boaz. Computational Complexity: A Modern Approach. Cambridge: Cambridge University Press, 2009.
ARORA, Sanjeev; LUND, Carsten. Hardness of Approximations. In: Approximation Algorithms for NP-Hard Problems. Boston: PWS Publishing, 1996.
AUSIELLO, Giorgio et al. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Berlin: Springer, 1999.
BAZARAA, Mokhtar S.; JARVIS, John J.; SHERALI, Hanif D. Linear Programming and Network Flows. 4th ed. Hoboken: John Wiley & Sons, 2010.
BERTSIMAS, Dimitris; TSITSIKLIS, John N. Introduction to Linear Optimization. Belmont: Athena Scientific, 1997.
BLUM, Christian; ROLI, Andrea. Metaheuristics in Combinatorial Optimization. ACM Computing Surveys, v. 35, n. 3, p. 268-308, 2003.
BRASIL. Base Nacional Comum Curricular: Ensino Médio. Brasília: MEC/CONSED/UNDIME, 2018.
CHVÁTAL, Vašek. Linear Programming. New York: W. H. Freeman, 1983.
COOK, William J. In Pursuit of the Traveling Salesman. Princeton: Princeton University Press, 2012.
CORMEN, Thomas H. et al. Introduction to Algorithms. 4th ed. Cambridge: MIT Press, 2022.
DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algorithms. Boston: McGraw-Hill, 2008.
DANTZIG, George B.; THAPA, Mukund N. Linear Programming. New York: Springer, 2003. 2 v.
DORIGO, Marco; STÜTZLE, Thomas. Ant Colony Optimization. Cambridge: MIT Press, 2004.
DU, Ding-Zhu; KO, Ker-I; HU, Xiaodong. Design and Analysis of Approximation Algorithms. New York: Springer, 2012.
FEIGE, Uriel. A Threshold of ln n for Approximating Set Cover. Journal of the ACM, v. 45, n. 4, p. 634-652, 1998.
GAREY, Michael R.; JOHNSON, David S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman, 1979.
GENDREAU, Michel; POTVIN, Jean-Yves (Eds.). Handbook of Metaheuristics. 3rd ed. Cham: Springer, 2019.
GLOVER, Fred; KOCHENBERGER, Gary A. (Eds.). Handbook of Metaheuristics. Boston: Kluwer Academic Publishers, 2003.
GOEMANS, Michel X.; WILLIAMSON, David P. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM, v. 42, n. 6, p. 1115-1145, 1995.
GOLDREICH, Oded. Computational Complexity: A Conceptual Perspective. Cambridge: Cambridge University Press, 2008.
GOLDBERG, David E. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading: Addison-Wesley, 1989.
GONZÁLEZ, Teofilo F. (Ed.). Handbook of Approximation Algorithms and Metaheuristics. 2nd ed. Boca Raton: CRC Press, 2018. 2 v.
GRAHAM, Ronald L. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, v. 17, n. 2, p. 416-429, 1969.
GRÖTSCHEL, Martin; LOVÁSZ, László; SCHRIJVER, Alexander. Geometric Algorithms and Combinatorial Optimization. 2nd ed. Berlin: Springer, 1993.
HÅSTAD, Johan. Some Optimal Inapproximability Results. Journal of the ACM, v. 48, n. 4, p. 798-859, 2001.
HOCHBAUM, Dorit S. (Ed.). Approximation Algorithms for NP-Hard Problems. Boston: PWS Publishing, 1996.
HOLLAND, John H. Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press, 1975.
JANSEN, Klaus; MARGRAF, Marian. Approximative Algorithmen und Nicht-Approximierbarkeit. Berlin: De Gruyter, 2008.
JOHNSON, David S. Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, v. 9, n. 3, p. 256-278, 1974.
KARMARKAR, Narendra. A New Polynomial-Time Algorithm for Linear Programming. Combinatorica, v. 4, n. 4, p. 373-395, 1984.
KARP, Richard M. Reducibility among Combinatorial Problems. In: Complexity of Computer Computations. New York: Plenum, 1972. p. 85-103.
KENNEDY, James; EBERHART, Russell. Particle Swarm Optimization. In: IEEE International Conference on Neural Networks, 1995. Proceedings.
KHOT, Subhash. On the Unique Games Conjecture. In: International Congress of Mathematicians, 2010. Proceedings.
KIRKPATRICK, Scott; GELATT, C. Daniel; VECCHI, Mario P. Optimization by Simulated Annealing. Science, v. 220, n. 4598, p. 671-680, 1983.
KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Boston: Pearson, 2006.
KORTE, Bernhard; VYGEN, Jens. Combinatorial Optimization: Theory and Algorithms. 6th ed. Berlin: Springer, 2018.
LAWLER, Eugene L. et al. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester: John Wiley & Sons, 1985.
LENSTRA, Jan Karel; RINNOOY KAN, Alexander H. G.; SHMOYS, David B. The Traveling Salesman Problem: A Computational Study. Princeton: Princeton University Press, 2007.
LOVÁSZ, László; PLUMMER, Michael D. Matching Theory. Providence: AMS Chelsea Publishing, 2009.
MOTWANI, Rajeev; RAGHAVAN, Prabhakar. Randomized Algorithms. Cambridge: Cambridge University Press, 1995.
NEMHAUSER, George L.; WOLSEY, Laurence A. Integer and Combinatorial Optimization. New York: John Wiley & Sons, 1988.
PAPADIMITRIOU, Christos H. Computational Complexity. Reading: Addison-Wesley, 1994.
PAPADIMITRIOU, Christos H.; STEIGLITZ, Kenneth. Combinatorial Optimization: Algorithms and Complexity. Mineola: Dover Publications, 1998.
RESENDE, Mauricio G. C.; RIBEIRO, Celso C. Optimization by GRASP. New York: Springer, 2016.
ROUGHGARDEN, Tim. Twenty Lectures on Algorithmic Game Theory. Cambridge: Cambridge University Press, 2016.
SCHRIJVER, Alexander. Theory of Linear and Integer Programming. Chichester: John Wiley & Sons, 1986.
SHMOYS, David B.; WILLIAMSON, David P. The Design of Approximation Algorithms. Cambridge: Cambridge University Press, 2011.
SIPSER, Michael. Introduction to the Theory of Computation. 3rd ed. Boston: Cengage Learning, 2013.
SPIELMAN, Daniel A.; TENG, Shang-Hua. Smoothed Analysis of Algorithms. Journal of the ACM, v. 51, n. 3, p. 385-463, 2004.
TALBI, El-Ghazali. Metaheuristics: From Design to Implementation. Hoboken: John Wiley & Sons, 2009.
TREVISAN, Luca. Approximation Algorithms for Unique Games. Theory of Computing, v. 4, p. 111-128, 2008.
VAZIRANI, Vijay V. Approximation Algorithms. 2nd ed. Berlin: Springer, 2003.
WILLIAMSON, David P.; SHMOYS, David B. The Design of Approximation Algorithms. Cambridge: Cambridge University Press, 2011.
WOLSEY, Laurence A. Integer Programming. 2nd ed. Hoboken: John Wiley & Sons, 2020.
WOEGINGER, Gerhard J. Exact Algorithms for NP-Hard Problems: A Survey. In: Combinatorial Optimization — Eureka, You Shrink! Berlin: Springer, 2003.