An efficient parameterized approximation scheme for the Star k-Hub Center

Autor(es)

Benedito, Marcelo P. L. ; Pedrosa, Lehilton L. C. ; Ferreira, CE ; Lee, O ; Miyazawa, FK

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 10-pg., 2021-01-01.

Resumo

In the STAR k-HUB CENTER (SkHC), given a connected edge-weighted graph G, a center c is an element of V(G) and integers k, r >= 0, one wants to select a set of hubs H subset of V(G)\{c} of size k and an assignment from vertices to hubs. The goal is to find a solution in which the length of the longest path connecting each pair of vertices through the assigned hubs and the center is at most r. This problem appears in many areas, such as telecommunication, aviation and logistics, where hubs represent cross-docking centers that consolidate demand between pairs of clients, and the network has a centralized design. This paper investigates the parameterized complexity of the underlying graph connectivity problem. First, we note that finding a (1.25 c)-approximation is W[2]-hard, for E > 0, when the parameter is the number of hubs k. Moreover, we show that the problem is W[1]-hard even when parameterized by k plus the vertex cover number of the graph. While this rules out an algorithm parameterized by the treewidth tw of the graph, as a positive result, we present an efficient parameterized approximation scheme. Namely, for every epsilon > 0, we have a (1 + epsilon)-approximation that runs in time O*((tw/epsilon)(O(tw))). (C) 2021 The Authors. Published by Elsevier B.V. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 19/10400-2 - Algoritmos de aproximação e parametrizados para problemas de conectividade de pares
• Beneficiário: Marcelo Pinheiro Leite Benedito
• Modalidade de apoio: Bolsas no Brasil - Doutorado