Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143144 | Operations Research Letters | 2007 | 6 Pages |
Abstract
We present a very simple way of derandomizing the algorithm proposed by Gupta, Kumar and Roughgarden for single source rent-or-buy by using the method of conditional expectation. Using the improved analysis of Eisenbrand, Grandoni and Rothvoß, our derandomized algorithm has an approximation guarantee of 3.28.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
David P. Williamson, Anke van Zuylen,