An Approximation Algorithm for the Two-Stage Distributionally Robust Facility Location Problem

被引：4
|
作者：
Wu, Chenchen [1 ]
Du, Donglei [2 ,3 ]
Xu, Dachuan [2 ]
机构：
[1] Tianjin Univ Technol, Coll Sci, Tianjin 300384, Peoples R China
[2] Beijing Univ Technol, Dept Appl Math, Beijing 100124, Peoples R China
[3] Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 9Y2, Canada
来源：
ADVANCES IN GLOBAL OPTIMIZATION | 2015年 / 95卷
关键词：
Facility location problem; Approximation algorithm; Distributionally robust optimization;
D O I：
10.1007/978-3-319-08377-3_11
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this paper, we introduce a model of distributionally robust facility location problem (DRFLP) under moment constraints up to the second order. We show, via duality theory of moment problems, that the linear relaxation of the DRFLP is equivalent to that of the standard uncapacitated facility location problem (UFLP). Consequently, any LP-based approximation algorithm for the UFLP implies an approximation algorithm for the DRFLP with the same approximation ratio.
引用
收藏
页码：99 / 107
页数：9
相关论文
共 50 条
  • [1] A distributionally robust optimization approach for two-stage facility location problems
    Gourtani, Arash
    Nguyen Tri-Dung
    Xu, Huifu
    EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION, 2020, 8 (02) : 141 - 172
  • [2] Approximation algorithm for squared metric two-stage stochastic facility location problem
    Jin Zhang
    Min Li
    Yishui Wang
    Chenchen Wu
    Dachuan Xu
    Journal of Combinatorial Optimization, 2019, 38 : 618 - 634
  • [3] Approximation algorithm for squared metric two-stage stochastic facility location problem
    Zhang, Jin
    Li, Min
    Wang, Yishui
    Wu, Chenchen
    Xu, Dachuan
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (02) : 618 - 634
  • [4] Two-stage robust facility location problem with drones
    Zhu, Tengkuo
    Boyles, Stephen D.
    Unnikrishnan, Avinash
    TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2022, 137
  • [5] APPROXIMATION ALGORITHM FOR TWO-STAGE STOCHASTIC FAULT-TOLERANT FACILITY LOCATION PROBLEM
    Zhang, Li
    Li, Qiaoliang
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2025, 21 (03) : 1735 - 1748
  • [6] An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties
    Shao J.
    Xu D.
    Journal of the Operations Research Society of China, 2013, 1 (3) : 339 - 346
  • [7] Two-stage Robust Facility Location Problem with Multiplicative Uncertainties and Disruptions
    Peng, Chun
    Li, Jinlin
    Wang, Shanshan
    2017 14TH INTERNATIONAL CONFERENCE ON SERVICES SYSTEMS AND SERVICES MANAGEMENT (ICSSSM), 2017,
  • [8] A Memetic Algorithm for Solving Two Variants of the Two-Stage Uncapacitated Facility Location Problem
    Miskovic, Stefan
    Stanimirovic, Zorica
    INFORMATION TECHNOLOGY AND CONTROL, 2013, 42 (02): : 131 - 149
  • [9] A simple and effective genetic algorithm for the two-stage capacitated facility location problem
    Fernandes, Diogo R. M.
    Rocha, Caroline
    Aloise, Daniel
    Ribeiro, Glaydston M.
    Santos, Enilson M.
    Silva, Allyson
    COMPUTERS & INDUSTRIAL ENGINEERING, 2014, 75 : 200 - 208
  • [10] A two-stage robust model for a reliable p-center facility location problem
    Du, Bo
    Zhou, Hong
    Leus, Roel
    APPLIED MATHEMATICAL MODELLING, 2020, 77 : 99 - 114
12345