An approximation algorithm for stochastic multi-level facility location problem with soft capacities

Chenchen Wu (), Donglei Du and Yue Kang
Additional contact information
Chenchen Wu: Tianjin University of Technology
Donglei Du: University of New Brunswick
Yue Kang: Beijing University of Technology

Journal of Combinatorial Optimization, No 0, 13 pages

Abstract: Abstract Facility location problem is one of the most important problems in the combinatorial optimization. The multi-level facility location problem and the facility location with capacities are important variants for the classical facility location problem. In this work, we consider the multilevel facility location problem with soft capacities in the uncertain scenario. The uncertainty setting means the location process is stochastic. We consider a two-stage model. The soft-capacities setting means each facility has multiple capacities by paying multiple opening cost. The multi-level setting means the client needs to connect to a path. We propose a bifactor $$ (1/\alpha ,6/(1-2\alpha ) )$$(1/α,6/(1-2α))-approximation algorithm for the stochastic multi-level facility location problem (SMLFLP), where $$ \alpha \in (0,0.5) $$α∈(0,0.5) is a given constant. Then, we reduce the stochastic multi-level facility location problem with soft capacities to SMLFLP. The reduction implies a $$ \left( 1/\alpha + 6/(1-2\alpha ) \right) $$1/α+6/(1-2α)-approximation algorithm. The ratio is 14.9282 when setting $$ \alpha = 0.183 $$α=0.183.

Keywords: Multi-level facility location; Approximation algorithm; Uncertainty; 90C27; 68W25; 90C05 (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00538-8 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::y::i::d:10.1007_s10878-020-00538-8

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

DOI: 10.1007/s10878-020-00538-8

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 ().