Approximation algorithms for <i>k</i>-level stochastic facility location problems

作     者：Melo, Lucas P. Miyazawa, Flavio K. Pedrosa, Lehilton L. C. Schouery, Rafael C. S. 

作者机构：Univ Estadual Campinas Inst Comp Campinas SP Brazil 

出 版 物：《JOURNAL OF COMBINATORIAL OPTIMIZATION》 (组合优化杂志)

年 卷 期：2017年第34卷第1期

页      面：266-278页

核心收录：

学科分类：12[管理学] 120202[管理学-企业管理（含：财务管理、市场营销、人力资源管理）] 0202[经济学-应用经济学] 02[经济学] 1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：FAPESP [2013/21744-8] CNPq 

主　　题：Approximation algorithm Multilevel facility location problem Stochastic problem 

摘      要：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.