Improved Approximation Algorithms for Multilevel Facility Location Problems
Alexander Ageev7 
| (7) |
Sobolev Institute of Mathematics, pr. Koptyuga 4, 630090 Novosibirsk, Russia |
Abstract
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 reduction together with recent approximation algorithms for the latter problem,
due to Jain, Mahdian & Saberi, leads to a 4.83-approximation algorithm for the metric multilevel facility location problem
and to a 9-approximation algorithm for a capacitated version of it (where facilities have soft capacities). In the class of
combinatorial algorithms these performance ratios improve on the previous ones due to Bumb and Kern (6 and 12 respectively).
Research was partially supported by the Russian Foundation for Basic Research, project codes 01-01-00786, 02-01-01153, by
INTAS, project code 00-217, and by the Programme “Universities of Russia”, project code UR.04.01.012.
References secured to subscribers.