A new approximation algorithm for the multilevel facility location problem

作     者：Gabor, Adriana F. van Ommeren, Jan-Kees C. W. 

作者机构：Erasmus Univ Inst Econometr NL-3000 DR Rotterdam Netherlands Univ Twente Fac Elect Engn Math & Comp Sci NL-7500 AE Enschede Netherlands 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2010年第158卷第5期

页      面：453-460页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：Facility location Approximation algorithms Randomized algorithms 

摘      要：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.