Improved approximation algorithms for multilevel facility location problems

摘要

We show that the metric multilevel facility location problem is polynomial-time reducible within a factor of 3 to the metric uncapacitated facility location problem. This leads to a combinatorial 4.83-approximation algorithm for the metric multilevel facility location problem and to a 9-approximation algorithm for a capacitated version of it. (C) 2002 Elsevier Science B.V. All rights reserved. [References: 19]