A new approximation algorithm for the multilevel facility location problem

被引：28
|
作者：
Gabor, Adriana F. [1 ]
van Ommeren, Jan-Kees C. W. [2 ]
机构：
[1] Erasmus Univ, Inst Econometr, NL-3000 DR Rotterdam, Netherlands
[2] Univ Twente, Fac Elect Engn Math & Comp Sci, NL-7500 AE Enschede, Netherlands
来源：
DISCRETE APPLIED MATHEMATICS | 2010年 / 158卷 / 05期
关键词：
Facility location; Approximation algorithms; Randomized algorithms;
D O I：
10.1016/j.dam.2009.11.007
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：453 / 460
页数：8
相关论文
共 50 条
  • [21] An approximation algorithm for the k-level stochastic facility location problem
    Wang, Zhen
    Du, Donglei
    Gabor, Adriana F.
    Xu, Dachuan
    OPERATIONS RESEARCH LETTERS, 2010, 38 (05) : 386 - 389
  • [22] An Approximation Algorithm for the Dynamic k-level Facility Location Problem
    Wang, Limin
    Zhang, Zhao
    Xu, Dachuan
    Zhang, Xiaoyan
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019, 2019, 11640 : 284 - 291
  • [23] New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem
    Behsaz, Babak
    Salavatipour, Mohammad R.
    Svitkina, Zoya
    ALGORITHMICA, 2016, 75 (01) : 53 - 83
  • [24] New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem
    Babak Behsaz
    Mohammad R. Salavatipour
    Zoya Svitkina
    Algorithmica, 2016, 75 : 53 - 83
  • [25] A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem
    Joachim Gehweiler
    Christiane Lammersen
    Christian Sohler
    Algorithmica, 2014, 68 : 643 - 670
  • [26] Improved approximation algorithms for the uncapacitated facility location problem
    Chudak, FA
    Shmoys, DB
    SIAM JOURNAL ON COMPUTING, 2003, 33 (01) : 1 - 25
  • [27] Improved approximation algorithms for multilevel facility location problems
    Ageev, AA
    OPERATIONS RESEARCH LETTERS, 2002, 30 (05) : 327 - 332
  • [28] Inapproximability of the Multilevel Uncapacitated Facility Location Problem
    Krishnaswamy, Ravishankar
    Sviridenko, Maxim
    ACM TRANSACTIONS ON ALGORITHMS, 2016, 13 (01)
  • [29] A 3-Approximation Algorithm for Uniform Capacitated Facility Location Problem with Penalties
    Bansal, Manisha
    Aggarwal, Seema
    Aggarwal, Geeta
    Gupta, Neelima
    JOURNAL OF ELECTRICAL SYSTEMS, 2024, 20 (07) : 461 - 468
  • [30] Improved primal-dual approximation algorithm for the Connected Facility Location problem
    Jung, Hyunwoo
    Hasan, Mohammad Khairul
    Chwa, Kyung-Yong
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2008, 5165 : 265 - 277
12345