Orientadores: Pedro Jussieu de Rezende, Flávio Keidi Miyazawa

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo: No problema de cobertura mínima por conjuntos (MSC - Minimum Set Cover), são dados um conjunto L de objetos e uma coleção R de conjuntos e deseja-se encontrar uma sub-coleção S de R que seja uma cobertura de L de custo mínimo, ou seja, L está contido na união de todo os conjuntos R de S com...

Resumo: No problema de cobertura mínima por conjuntos (MSC - Minimum Set Cover), são dados um conjunto L de objetos e uma coleção R de conjuntos e deseja-se encontrar uma sub-coleção S de R que seja uma cobertura de L de custo mínimo, ou seja, L está contido na união de todo os conjuntos R de S com a soma dos custos dos conjuntos R de S sendo mínima. Entre as variantes desse problema, existem aquelas advindas de configurações geométricas, em que tanto os elementos de L quanto os conjuntos contidos em R são objetos geométricos. Como tais problemas são, em geral, NP-difíceis, se P ? NP, não é possível encontrar algoritmos exatos de tempo polinomial para os mesmos. Assim, torna-se interessante a busca por algoritmos aproximados eficientes para obtenção de soluções com garantia de qualidade. Nesta dissertação, estudamos diferentes versões do problema de cobertura mínima por discos (MDC ¿ Minimum Disk Cover), em que o conjunto R é um conjunto de discos, e o objetivo é projetar algoritmos aproximados. Tais versões do problema estão relacionadas com a solução de problemas práticos, como o posicionamento de estações-base em projeto de redes sem fio ou de dispositivos em redes de sensores. Para o caso em que o conjunto de objetos geométricos L é constituído de um único segmento de reta no plano, apresentamos um FPTAS. Para outra versão mais geral, na qual o conjunto de objetos geométricos é dado por um sistema de inequações polinomiais algébricas, propomos um algoritmo aproximado, o qual demonstramos ser um PTAS

Abstract: The Minimum Set Cover problem (MSC) can be described as: given a set L of elements and a collection of sets R, find a subcollection S of R that is a minimum-cost covering for L, i.e., L is contained in the union of the sets R in S, and the sum of the costs of the sets R in S is minimum....

Abstract: The Minimum Set Cover problem (MSC) can be described as: given a set L of elements and a collection of sets R, find a subcollection S of R that is a minimum-cost covering for L, i.e., L is contained in the union of the sets R in S, and the sum of the costs of the sets R in S is minimum. Among the variants of this problem, there are those that arise from a geometric configuration in which both the elements of L and the sets contained in R are geometric objects. As such problems are, in general, NP-hard, if P ? NP, it is impossible to find polynomial-time exact algorithms for them. Thus, the use of efficient approximation algorithms to find high quality solutions becomes a good approach. In this dissertation, we study different versions of the Minimum Disk Cover problem (MDC), in which the sets in R are disks, and we seek to develop approximation algorithms. These versions are related to practical problems, such as base station positioning problem for wireless network design and placement of devices in a sensor network. For the case in which the set of geometric objects to be covered is given by a single line segment, we present an FPTAS. For a more general case, where the set of geometric objects is given by a system of algebraic polynomial inequalities, we propose an approximation algorithm which we prove to be a PTAS