| Texto completo | |
| Autor(es): |
Benedito, Marcelo P. L.
;
Melo, Lucas P.
;
Pedrosa, Lehilton L. C.
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | LATIN 2022: THEORETICAL INFORMATICS; v. 13568, p. 16-pg., 2022-01-01. |
| Resumo | |
In the Multiple Allocation k-Hub Center, we are given a connected edge-weighted graph G, sets of clients C and hub locations H, where V (G) = C boolean OR H, a set of demands D subset of C-2 and a positive integer k. A solution is a set of hubs H subset of H of size k such that every demand (a, b) is satisfied by a path starting in a, going through some vertex of H, and ending in b. The objective is to minimize the largest length of a path. We show that finding a (3 - epsilon)-approximation is NP-hard already for planar graphs. For arbitrary graphs, the approximation lower bound holds even if we parameterize by k and the value r of an optimal solution. An exact FPT algorithm is also unlikely when the parameter combines k and various graph widths, including pathwidth. To confront these hardness barriers, we give a (2 + epsilon)-approximation algorithm parameterized by treewidth, and, as a byproduct, for unweighted planar graphs, we give a (2 + epsilon)-approximation algorithm parameterized by k and r. Compared to classical location problems, computing the length of a path depends on non-local decisions. This turns standard dynamic programming algorithms impractical, thus our algorithm approximates this length using only local information. (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 |