Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Approximation algorithms for Median Hub Location Problems

Texto completo
Autor(es):
Benedito, Marcelo P. L. [1] ; Pedrosa, Lehilton L. C. [1]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 38, n. 2, p. 375-401, AUG 2019.
Citações Web of Science: 0
Resumo

In Hub Location Problems, an input is composed of sets of clients, locations and a pairs of clients; a solution is a subset of locations to open hubs and an assignment for each pair of clients to a route starting in the first client, passing through one or more hubs and ending in the second client. The objective is to find a solution that minimizes the length of all routes plus the cost of opening hubs. The currently known approximation algorithms consider only the case in which the set of hubs is given as part of the input and the problem is assigning clients to hubs. For a metric space setting, this work presents the first constant-factor approximation algorithms for the problem of, simultaneously, selecting hubs and allocating clients. A few variants are considered, depending on whether the number of open hubs is given in the input or a client must be assigned to a single hub. In particular, we give an LP-rounding 2.48-approximation algorithm for the Single-Allocation Median Hub Location Problem, using a new formulation and exploiting its symmetries. (AU)

Processo FAPESP: 16/12006-1 - Algoritmos de aproximação para problemas de localização e alocação de terminais
Beneficiário:Marcelo Pinheiro Leite Benedito
Linha de fomento: Bolsas no Brasil - Mestrado
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
Linha de fomento: Auxílio à Pesquisa - Temático