To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Effective Algorithm CFL Based on Steiner Tree and UFL Problem |
|
Author |
Hong-Zhen Zheng, Dian-Hui Chu, De-Chen Zhan |
| Citation |
Vol. 6 No. 9 pp. 24-27 |
|
Abstract |
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 |
|
Keywords |
UFL, Steiner tree,CFl, network design |
|
URL |
