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 条
  • [31] A constant factor approximation algorithm for the fault-tolerant facility location problem
    Guha, S
    Meyerson, A
    Munagala, K
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2003, 48 (02): : 429 - 440
  • [32] An efficient approximation algorithm for the extension facility location problem on torus internetwork topology
    Shu, Wenhao
    Qian, Wenbin
    Yang, Jun
    INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND MATHEMATICS, 2018, 9 (02) : 189 - 196
  • [33] An Algorithm to solve a Facility Location Problem using a Discrete Approximation to the Voronoi Diagram
    Trefftz, Christian
    DeVries, Byron
    Jenkins, Benjamin
    2021 IEEE INTERNATIONAL CONFERENCE ON ELECTRO INFORMATION TECHNOLOGY (EIT), 2021, : 86 - 90
  • [34] AN APPROXIMATION ALGORITHM FOR THE k-LEVEL FACILITY LOCATION PROBLEM WITH SUBMODULAR PENALTIES
    Li, Gaidi
    Wang, Zhen
    Xu, Dachuan
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2012, 8 (03) : 521 - 529
  • [35] Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties
    Yang, Pei-Jia
    Luo, Wen-Chang
    JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA, 2025, 13 (01) : 287 - 296
  • [36] An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
    Asadi, Mohsen
    Niknafs, Ali
    Ghodsi, Mohammad
    ADVANCES IN COMPUTER SCIENCE AND ENGINEERING, 2008, 6 : 41 - 49
  • [37] The approximation gap for the metric facility location problem is not yet closed
    Byrka, Jaroslaw
    Aardal, Karen
    OPERATIONS RESEARCH LETTERS, 2007, 35 (03) : 379 - 384
  • [38] An Improved Approximation Algorithm for the k-Level Facility Location Problem with Soft Capacities
    Chen-chen WU
    Da-chuan XU
    Acta Mathematicae Applicatae Sinica, 2017, 33 (04) : 1015 - 1024
  • [39] A local search approximation algorithm for the uniform capacitated k-facility location problem
    Lu Han
    Dachuan Xu
    Donglei Du
    Dongmei Zhang
    Journal of Combinatorial Optimization, 2018, 35 : 409 - 423
  • [40] A 3-approximation algorithm for the k-level uncapacitated facility location problem
    Aardal, K
    Chudak, FA
    Shmoys, DB
    INFORMATION PROCESSING LETTERS, 1999, 72 (5-6) : 161 - 167
12345