Please use this identifier to cite or link to this item:
Type: Artigo
Title: Approximation Algorithms For K-level Stochastic Facility Location Problems
Author: Melo L.P.
Miyazawa F.K.
Pedrosa L.L.C.
Schouery R.C.S.
Abstract: 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 (Formula presented.)-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 (Formula presented.), the algorithm achieves factors 2.56 and 2.78, resp., which improves the (Formula presented.)-approximation for (Formula presented.) 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 (Formula presented.), and (Formula presented.) in general. © 2016 Springer Science+Business Media New York
Subject: Approximation Algorithm
Multilevel Facility Location Problem
Stochastic Problem
Editor: Springer New York LLC
Rights: fechado
Identifier DOI: 10.1007/s10878-016-0064-2
Date Issue: 2016
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
2-s2.0-84982131414.pdf477.57 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.