Article ID Journal Published Year Pages File Type
1143144 Operations Research Letters 2007 6 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
Authors
, ,