Algoritmos de aproximação e parametrizados para problemas de conectividade de pares

• Processo: 19/10400-2
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de fevereiro de 2020
• Data de Término da vigência: 20 de novembro de 2022
• Á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: Marcelo Pinheiro Leite Benedito
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
• Assunto(s): Algoritmos de aproximação Problemas de localização de facilidades Conectividade
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Algoritmos parametrizados | problemas de conectividade | Problemas de localização | Algoritmos de aproximação e parametrizados

Resumo

Os problemas de conectividade de pares formam uma vertente dos problemas de localização, em que devemos posicionar estruturas de forma a satisfazer restrições de conexão entre pares de pontos de rede. Diversos problemas de interesse prático podem ser assim classificados, como o problema da localização e alocação de terminais (HLP), em que temos que atender demandas entre pares de clientes através de terminais de uma rede, com todo o fluxo de produtos passando por eles. Com variantes desse problema, podemos modelar aplicações em setores de transporte aéreo, distribuição de produtos e transporte público. Neste projeto, estamos interessados em estudar problemas de conectividade de pares levando em conta suas principais variantes e parâmetros. Iremos desenvolver algoritmos de aproximação e algoritmos parametrizados, assim como resultados de inaproximabilidade e de dificuldade associados. Este trabalho irá lidar com uma grande combinação de problemas e técnicas algorítmicas, particularmente aquelas que correspondem a questões em aberto, apesar do grande número de trabalhos e referências sobre esses e outros problemas de localização. Por exemplo, enquanto existem algoritmos de aproximação para alguns casos do HLP, desenvolvidos pelo candidato durante seu mestrado, não são conhecidas aproximações para diversas outras variantes, nem há trabalhos que o estudam sob o ponto de vista de complexidade parametrizada. Além disso, esperamos investigar algoritmos de aproximação parametrizados, uma área recente da literatura que une as duas abordagens a fim de tratar problemas que são difíceis para cada uma separadamente, constituindo assim uma boa oportunidade de realizar pesquisa inovadora. (AU)

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)

BENEDITO, MARCELO P. L.; PEDROSA, LEHILTON L. C.; FERREIRA, CE; LEE, O; MIYAZAWA, FK. An efficient parameterized approximation scheme for the Star k-Hub Center. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 10-pg., 2021-01-01. (15/11937-9, 19/10400-2)

BENEDITO, MARCELO P. L.; PEDROSA, LEHILTON L. C.; ROSADO, HUGO K. K.; FERREIRA, CE; LEE, O; MIYAZAWA, FK. On the Inapproximability of the Cable-Trench Problem. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 10-pg., 2021-01-01. (15/11937-9, 19/10400-2)

BENEDITO, MARCELO P. L.; PEDROSA, LEHILTON L. C.; ROSADO, HUGO K. K.. On the complexity of the Cable-Trench Problem. DISCRETE APPLIED MATHEMATICS, v. 340, p. 14-pg., 2023-12-15. (15/11937-9, 19/10400-2)

Publicações acadêmicas

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

BENEDITO, Marcelo Pinheiro Leite. Approximation and parameterized algorithms for pair connectivity problems. 2023. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.