Orientadores: Pedro Jussieu de Rezende, Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:56:08Z (GMT). No. of bitstreams: 1
Sasaki_AndersonToshiyuki_M.pdf: 1449279 bytes, checksum: 851c64c64afd4605cbfb4946ed5f97a4 (MD5)
Previous issue date: 2014 / 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. 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 / Mestrado / Ciência da Computação / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/275515 |
| Date | 25 August 2018 |
| Creators | Sasaki, Anderson Toshiyuki, 1988- |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Miyazawa, Flávio Keidi, 1970-, Rezende, Pedro Jussieu de, 1955-, Meira, Luis Augusto Angelotti, Xavier, Eduardo Candido |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 57 f. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds