Approximation and parameterized algorithms for pair connectivity problems

• Grant number: 19/10400-2
• Support Opportunities: Scholarships in Brazil - Doctorate
• Effective date (Start): February 01, 2020
• Effective date (End): November 20, 2022
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Lehilton Lelis Chaves Pedrosa
• Grantee: Marcelo Pinheiro Leite Benedito
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

Pair connectivity problems are a branch of location problems, in which weposition structures in order to satisfy connectivity constraints between pairs of points in a network. Many problems with practical interest can be classified as this, like the Hub Location Problem (HLP), in which demands between pairs of clients must be connected using network terminals, with the product flow passing through them. Employing this problem's variants, we can model applications in the air traffic sector, as well as product distribution and public transport. In this project, we are interested in studying pair connectivity problems with its main variants and parameters. We will develop approximation algorithms and parameterized algorithms, alongside with associated inapproximability and hardness results. This project will deal with a wide combination of problems and algorithmic techniques, particularly those involved in the open questions of the field, although there is a great number of related work and references about these and other location problems. For instance, admitting there exists approximation algorithms for some cases of HLP, developed during the candidate's masters, other variants still don't have any approximation related work, norstudies in a parameterized complexity point of view. Furthermore, we hope to investigate parameterized approximation algorithms, a recent area that combine these two approaches in order to deal with problems that are hard for each one separately, constituting a good opportunity to perform innovative research. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

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)

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)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

BENEDITO, Marcelo Pinheiro Leite. Algoritmos de aproximação e parametrizados para problemas de conectividade de pares. 2023. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.