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 条
  • [41] A local search approximation algorithm for a squared metric k-facility location problem
    Zhang, Dongmei
    Xu, Dachuan
    Wang, Yishui
    Zhang, Peng
    Zhang, Zhenning
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (04) : 1168 - 1184
  • [42] An Improved Approximation Algorithm for the k-Level Facility Location Problem with Soft Capacities
    Wu, Chen-chen
    Xu, Da-chuan
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2017, 33 (04): : 1015 - 1024
  • [43] A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
    Jung, Hyunwoo
    Hasan, Mohammad Khairul
    Chwa, Kyung-Yong
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (03) : 258 - 271
  • [44] A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
    Hyunwoo Jung
    Mohammad Khairul Hasan
    Kyung-Yong Chwa
    Journal of Combinatorial Optimization, 2009, 18 : 258 - 271
  • [45] A Local Search Approximation Algorithm for a Squared Metric k-Facility Location Problem
    Zhang, Dongmei
    Xu, Dachuan
    Wang, Yishui
    Zhang, Peng
    Zhang, Zhenning
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT I, 2017, 10627 : 119 - 124
  • [46] A local search approximation algorithm for a squared metric k-facility location problem
    Dongmei Zhang
    Dachuan Xu
    Yishui Wang
    Peng Zhang
    Zhenning Zhang
    Journal of Combinatorial Optimization, 2018, 35 : 1168 - 1184
  • [47] An improved approximation algorithm for the k-level facility location problem with soft capacities
    Chen-chen Wu
    Da-chuan Xu
    Acta Mathematicae Applicatae Sinica, English Series, 2017, 33 : 1015 - 1024
  • [48] Approximation Algorithms for Bounded Facility Location Problems
    Piotr Krysta
    Roberto Solis-Oba
    Journal of Combinatorial Optimization, 2001, 5 : 233 - 247
  • [49] Approximation algorithms for bounded facility location problems
    Krysta, P
    Solis-Oba, R
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2001, 5 (02) : 233 - 247
  • [50] Approximation Algorithms for a Facility Location Problem with Service Capacities
    Massberg, Jens
    Vygen, Jens
    ACM TRANSACTIONS ON ALGORITHMS, 2008, 4 (04)
12345