Algoritmos Parametrizados para o Freeze-Tag Problem sobre Diferentes Domínios

• Processo: 22/13435-4
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2023
• Data de Término da vigência: 31 de janeiro de 2025
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Lehilton Lelis Chaves Pedrosa
• Beneficiário: Lucas de Oliveira Silva
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Bolsa(s) vinculada(s): 23/12529-8 - Algoritmos para o freeze-tag e problemas de robótica de enxame relacionados, BE.EP.MS
• Assunto(s): Otimização combinatória Problemas de escalonamento
• Palavra(s)-Chave do Pesquisador: Algoritmos parametrizados | Complexidade de Algoritmos | Freeze-Tag Problem | Otimização Combinatória | Problemas de Escalonamento | Problemas em Grafos | Complexidade de Algoritmos

Resumo

Problemas de ativação de robôs aparecem naturalmente no contexto de robótica de enxame. Em particular, o Freeze-Tag Problem (FTP) consiste em ativar um conjunto de robôs dormentes a partir de um único robô, que está inicialmente ativo, que se desloca até a localização daqueles dormentes para ativá-los. Quando um robô é ativado, ele pode ajudar a ativar outros robôs ainda dormentes. O objetivo é encontrar uma estratégia para ativar todo o conjunto no menor tempo possível, i.e., que minimize o makespan.Esse problema é NP-difícil e já foi bastante explorado sob a ótica de algoritmos de aproximação ou meta-heurísticas, tanto na versão geométrica quanto na versão em que a entrada é um grafo. No entanto, são raros os trabalhos na literatura que lidam com o FTP sob a perspectiva de algoritmos parametrizados.A motivação para estudar algoritmos parametrizados é que, embora não existam algoritmos polinomiais para um problema NP-difícil, na hipótese de que P seja diferente de NP, frequentemente, as instâncias consideradas na prática têm algum parâmetro estrutural fixo (e.g., grau máximo do grafo). Isso sugere buscar algoritmos cujo tempo de execução é um polinômio multiplicado por uma função que depende apenas do parâmetro. Quando isso é possível, dizemos que o problema é Fixed-Parameter Tractable (FPT), ou seja, polinomial ao limitar tal parâmetro. O objetivo deste projeto é determinar parâmetros para os quais o Freeze-Tag Problem é FPT tanto no domínio geométrico quanto em grafos.

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

CHAVES PEDROSA, LEHILTON LELIS; SILVA, LUCAS DE OLIVEIRA. Freeze-Tag is NP-hard in 3D with L₁ distance. XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, v. 224, p. 7-pg., 2023-01-01. (22/13435-4)