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 k-level stochastic facility location problems

Texto completo
Autor(es):
Melo, Lucas P. ; Miyazawa, Flavio K. ; Pedrosa, Lehilton L. C. ; Schouery, Rafael C. S.
Número total de Autores: 4
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 34, n. 1, p. 266-278, JUL 2017.
Citações Web of Science: 1
Resumo

In the k-level facility location problem (FLP), we are given a set of facilities, each associated with one of k levels, and a set of clients. We have to connect each client to a chain of opened facilities spanning all levels, minimizing the sum of opening and connection costs. This paper considers the k-level stochastic FLP, with two stages, when the set of clients is only known in the second stage. There is a set of scenarios, each occurring with a given probability. A facility may be opened in any stage, however, the cost of opening a facility in the second stage depends on the realized scenario. The objective is to minimize the expected total cost. For the stage-constrained variant, when clients must be served by facilities opened in the same stage, we present a -approximation, improving on the 4-approximation by Wang et al. (Oper Res Lett 39(2):160-161, 2011) for each k. In the case with , the algorithm achieves factors 2.56 and 2.78, resp., which improves the -approximation for by Wu et al. (Theor Comput Sci 562:213-226, 2015). For the non-stage-constrained version, we give the first approximation for the problem, achieving a factor of 3.495 for the case with , and in general. (AU)

Processo FAPESP: 13/21744-8 - Abordagens teóricas e práticas para problemas de empacotamento
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Bolsas no Brasil - Pós-Doutorado