Algoritmos aproximados para cobertura de objetos geométricos por discos

No problema de cobertura minima por conjuntos (MSC - Minimum Set Cover), sao dados um conjunto L de objetos e uma colecao R de conjuntos e deseja-se encontrar uma sub-colecao S de R que seja uma cobertura de L de custo minimo, ou seja, L esta contido na uniao de todo os conjuntos R de S com a soma dos custos dos conjuntos R de S sendo minima. Entre as variantes desse problema, existem aquelas advindas de configuracoes geometricas, em que tanto os elementos de L quanto os conjuntos contidos em R sao objetos geometricos. Como tais problemas sao, em geral, NP-dificeis, se P ≠ NP,, nao e possivel encontrar algoritmos exatos de tempo polinomial para os mesmos. Assim, torna-se interessante a busca por algoritmos aproximados eficientes para obtencao de solucoes com garantia de qualidade. Nesta dissertacao, estudamos diferentes versoes do problema de cobertura minima por discos (MDC - Minimum Disk Cover), em que o conjunto R e um conjunto de discos, e o objetivo e projetar algoritmos aproximados. Tais versoes do problema estao relacionadas com a solucao de problemas praticos, como o posicionamento de estacoes-base em projeto de redes sem fio ou de dispositivos em redes de sensores. Para o caso em que o conjunto de objetos geometricos L e constituido de um unico segmento de reta no plano, apresentamos um FPTAS. Para outra versao mais geral, na qual o conjunto de objetos geometricos e dado por um sistema de inequacoes polinomiais algebricas, propomos um algoritmo aproximado, o qual demonstramos ser um PTAS. Abstract