Approximation algorithms for k-level stochastic facility location problems

Lucas P. Melo (), Flávio K. Miyazawa (), Lehilton L. C. Pedrosa () and Rafael C. S. Schouery ()
Additional contact information
Lucas P. Melo: Universidade Estadual de Campinas
Flávio K. Miyazawa: Universidade Estadual de Campinas
Lehilton L. C. Pedrosa: Universidade Estadual de Campinas
Rafael C. S. Schouery: Universidade Estadual de Campinas

Journal of Combinatorial Optimization, 2017, vol. 34, issue 1, No 19, 266-278

Abstract: 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 $$(4-o(1))$$ ( 4 - o ( 1 ) ) -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 $$k=2,\,3$$ k = 2 , 3 , the algorithm achieves factors 2.56 and 2.78, resp., which improves the $$(3+\epsilon )$$ ( 3 + ϵ ) -approximation for $$k=2$$ k = 2 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 $$k = 2$$ k = 2 , and $$2k-1+o(1)$$ 2 k - 1 + o ( 1 ) in general.

Keywords: Approximation algorithm; Multilevel facility location problem; Stochastic problem (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0064-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:1:d:10.1007_s10878-016-0064-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0064-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().