An Approximation Algorithm for the Dynamic k-level Facility Location Problem

摘要

In this paper, we consider the dynamic k-level facility location problem, which is a generalization of the uncapacitated k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for the problem which finds a solution within 6 times the optimum. This approximation ratio under a dynamic setting coincides with that of the simple dual ascent 6-approximation algorithm for the (static) multilevel facility location problem (Bumb, 2001) with a weak triangle inequality property.