Algoritmos para problemas sobre cobertura por sensores.

• Processo: 09/03589-0
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de agosto de 2009
• Data de Término da vigência: 28 de fevereiro de 2011
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Yoshiko Wakabayashi
• Beneficiário: Rafael da Ponte Barbosa
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Otimização combinatória Complexidade computacional Algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos | cobertura de faixa por sensores | cobertura por sensores | Complexidade Computacional | razão de aproximação | Otimização Combinatória

Resumo

Este projeto se insere na área de otimização combinatória e tem como foco central a investigação de algoritmos para problemas sobre cobertura por sensores.O problema que será objeto de nossa pesquisa, chamado problema da cobertura por sensores, na sua forma mais geral pode ser formulado da seguinte maneira. Considere um conjunto ${\mathcal S}$ de sensores e uma região ${\mathcal R}$ a ser coberta por esses sensores. Suponha que para cada sensor $s\in{\mathcal S}$ são dados uma região $R(s)$ que esse sensor cobre (uma subregião de ${\mathcal R}$) e um tempo de duração $d_s$ durante o qual este sensor permanece funcionando. Deseja-se encontrar, para cada sensor $s$, o tempo de início $t(s)$, momento em que o sensor~$s$ deve ser ligado, de modo a maximizar o intervalo de tempo durante o qual a região original ${\mathcal R}$ permanece coberta.Este problema foi estudado por Buchsbaum, Efrat, Jain, Venkatasubramanian e Yi [SODA 2007], que também apresentaram resultados sobre casos especiais do problema. O caso unidimensional, que será objeto de nossos estudos, trata da cobertura de sensores ao longo de uma linha (um intervalo da reta real). Aqui, cada sensor pode ser visto como um retângulo de base igual ao intervalo de cobertura e altura igual a sua duração. Podemos considerar que, inicialmente, cada retângulo tem a sua base posicionada paralelamente ao eixo horizontal, ocupando exatamente a posição dada pelos pontos que definem sua base. Temos assim vários retângulos que se sobrepõem, e o objetivo é mover cada retângulo apenas na vertical --- ortogonalmente em relação ao eixo horizontal --- de modo a manter totalmente coberta a maior área possível (permitindo-se que vários dos retângulos fiquem sobrepostos). Este caso é conhecido como problema restrito da cobertura de faixa (restricted strip covering). Outros problemas relacionados têm sido investigados por Buchsbaum, Karloff, Kenyon, Reingold e Thorup [SIAM J. Comput. 2004], por Feige, Halldórsson, Kortsarz e Srinivasan [SIAM J. Comput. 2002], Perillo e Heinzelman [IEEE WCNC2003].O foco do projeto consiste em fazer um estudo bem abrangente, sob o ponto de vista algorítmico, dos vários resultados sobre o problema central e suas variantes. Uma das metas é produzir uma resenha completa e atualizada sobre o tópico. Algoritmos de aproximação e questões sobre a complexidade computacional serão abordados nessa resenha. Após cumprir essa meta, o aluno poderá dedicar-se ao estudo de problemas em aberto, como por exemplo, obter um algoritmo com melhor razão de desempenho para o caso unidimensional e tentar (des)provar a existência de PTAS para esse caso. Neste projeto de mestrado a ênfase será dada na formação geral do aluno: a pesquisa proposta, complementada pelas disciplinas que o aluno irá cursar, objetiva dar ao aluno uma formação sólida na área de otimização combinatória, algoritmos e complexidade computacional.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

BARBOSA, Rafael da Ponte. Algoritmos para o problema da cobertura por sensores. 2011. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.