Dois problemas de otimização em grafos: Transporte em redes de dutos e Busca com custos de acesso - Pessoa, Artur Alves; Milidiú, Ruy Luiz; Laber, Eduardo Sany (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2004: Anais do XVII Concurso de Teses e Dissertações, 2004)
Consideramos dois problemas de otimização combinatória bastante distintos: o problema de transporte em redes de dutos (PTD) e o problema de busca com custos de acesso (PBC). O PTD utiliza um novo modelo simplificado, baseado nas operações dos oleodutos da Petrobras. Também definimos diversas variações deste problema. Para a variação mais genérica, provamos que encontrar uma solução viável é NP-difícil. Para outra, mostramos que a minimização dos custos de transporte dutoviário, pode ser resolvida em tempo polinomial. Neste caso, também provamos que a minimização do makespan é difícil de aproximar. O PBC considera a busca por um elemento num vetor ordenado com custos de acesso variados. Apresentamos algoritmos lineares (2 + e + o(1)) -aproximados para minimizar o custo da pior busca ou o custo médio de uma busca. Também apresentamos um algoritmo O(log n) -aproximado para o custo médio que apresenta um desempenho muito bom para alguns casos práticos testados, onde é o tamanho da entrada.