Esta dissertação trata do método primal-dual e de suas aplicações no projeto de algoritmos em otimização combinatória. Dá-se o adjetivo de primal-dual aos algoritmos que usam o método como 'protótipo'. Vários problemas são resolvidos completa e eficientemente por algoritmos primal-duais. Entretanto, para muitos problemas importantes em otimização combinatória somos forçados a explorar possibilidades menos ambiciosas. Entre esses algoritmos menos ambiciosos estão os chamados algoritmos de aproximação. Nesta dissertação também é descrito como o método primal-dual é usado no projeto de algoritmos de aproximação

not available