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: 2812
Download times: 2057
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



Top Paper  |  FAQ  |  Guest Editors  |  Email Alert  |  Links  |  Copyright  |  Contact Us

© Copyright by Institute of Software, the Chinese Academy of Sciences

京公网安备 11040202500065号