Algorithms for Min-Max p-hub location problems and variants

• Grant number: 18/00910-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2018
• Status: Discontinued
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Lehilton Lelis Chaves Pedrosa
• Grantee: Vinícius Balbino de Souza
• 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

In several applications (e.g., transport, logistics, telecommunications, postal services and distribution networks), we need to install hubs, such as terminal airports or network switches. A hub is a consolidation and exchange center which allows direct connection, using a smaller number of indirect connections. In this project, we will study the hub allocation problems and variants. An example is the so-called p-hub center problem, which consists in determining p vertices of a network to serve the demand for flow between pairs of nodes, and such that it minimizes the largest cost between source and destination. Many of these problems are NP-hard, and therefore we will examine especially approximation algorithms. We will study existing techniques and variants and consider particular cases of the problem, with the goal of establishing their computational complexity and designing new approximations. In particular, we will study the version of the capacitated p-hub center problem with hard capacities, i.e., when a terminal at a given location can serve only a given number of demands. (AU)