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 条
12345