文章基本信息

标题：Effective Algorithm CFL Based on Steiner Tree and UFL Problem
本地全文：下载
作者：Hong-Zhen Zheng ; Dian-Hui Chu, De-Chen,Zhan
期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2006
卷号：6
期号：9A
页码：24-27
出版社：International Journal of Computer Science and Network Security
摘要：In the field of approximation algorithms，a lot of earlier work on facility location problems and network design problems have sought to address these two questions independently .In this paper we present an integrated study of the overall Problem and study the problem in a integrated way that one to exploit the saving that may result from making both decision in a coordinated way to reduce the total cost of location and transportation. We provides approximation algorithms for some simple versions of the integrated problem to cover the gap. We present a + approximation algorithm for the capacitated facility location problem (CFL in short), where is any approximation factor achievable for the problem P. We do this by carefully combining solutions to appropriately set up Steiner tree and the uncapacitated facility location problems (UFL in short) that capture two natural lower bounds for our problem. With the current best approximation factors, this is a 3.07-approximation algorithm. Again, with the current best results, this gap is less than 5. For the case where clients have arbitrary demands and the entire demand for a client must be served by the same facility, we provide a + 2 approximation, which is currently at most 4.59
关键词：UFL, Steiner tree,CFl, network design