Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Improved Approximation Algorithms for Multilevel Facility Location Problems

Alexander AgeevContact Information

(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.

Contact Information Alexander Ageev
Email: ageev@math.nsc.ru
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.105 • Server: mpweb20
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)