ESSEC Working Papers,
ESSEC Research Center, ESSEC Business School

Abstract: An NP-hard variant of the single-source Capacitated Facility Location Problem is studied, where each facility is composed of a variable number of fixed-capacity production units. This problem, especially the metric case, has been recently studied in several papers. In this paper, we only consider the general problem where connection costs do not systematically satisfy the triangle inequality property. We show that an adaptation of the set covering greedy heuristic, where the sub-problem is approximately solved by a Fully Polynomial-Time Approximation Scheme based on cost scaling and dynamic programming, achieves a logarithmic approximation ratio of (1+ƒÕ)H(n) for the problem, where n is the number of clients to be served, and H is the harmonic series. This improves the previous bound of 2H(n) for this problem.

Keywords: Facility Location; Combinatorial optimization; Set Covering; Dynamic Programming; Approximation

JEL-codes: C44; C61

17 pages, March 2005

Full text files

showDeclFileRes.do?declId=3996&key=__workpaper__  

Download statistics

• ESSEC Research Center, ESSEC Business School
• Home page for this series

Questions (including download problems) about the papers in this series should be directed to Sophie Magnanou ()
Report other problems with accessing this service to Sune Karlsson ().

RePEc:ebg:essewp:dr-05003This page generated on 2024-10-19 15:41:33.