| Rent-or-Buy Network Design Problem and the Sample-Augment Algorithm: A Survey |
| Download PDF |
| Peng Zhang. Rent-or-Buy Network Design Problem and the Sample-Augment Algorithm: A Survey. International Journal of Software and Informatics, 2011,5(4):607~636 |
| Hits: 3115 |
| Download times: 2423 |
|
| Fund:This work is sponsored by the National Natural Science Foundation of China under Grant No.60970003, China Postdoctoral Science Foundation under Grant Nos.20080441144, 200902562, and the Special Foundation of Shandong Province Postdoctoral Innovation Projects under Grant No.200901010. |
|
| Abstract:The Rent-or-Buy Network Design problem is a fundamental connectivity-related network design problem. The problem captures the "economies of scale" property, which says that the per-unit cost of installing capacity on edges of the network decreases as more capacity is installed. The Sample-Augment algorithm is a simple but powerful randomized
approximation algorithm that effectively deals with the Rent-or-Buy and related problems. In this paper we systematically survey the Rent-or-Buy problem and the Sample-Augment algorithm, as well as its two analysis techniques, i.e., the cost-sharing method and the core-detouring scheme. |
| keywords:Rent-or-Buy Sample-Augment Cost-Sharing Core-Detouring network design approximation algorithm |
| View Full Text View/Add Comment Download reader |
