Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949962 | Discrete Applied Mathematics | 2016 | 13 Pages |
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
Andreas Bley, Mohsen Rezapour,