Article ID Journal Published Year Pages File Type
4949962 Discrete Applied Mathematics 2016 13 Pages PDF
Abstract
In this paper, we introduce and analyze two fundamental versions of these problems. In the Buy-at-Bulk version of the problem, each access cable type has a fixed setup cost and a fixed capacity, whereas in the Deep-Discount problem version, each cable type has unlimited capacity but a traffic-dependent variable cost in addition to its fixed setup cost. We derive the first constant-factor approximation algorithms for these problems, using different algorithmic and analytical techniques.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,