A simpler and better derandomization of an approximation algorithm for single source rent-or-buy |
| |
| Authors: | David P. Williamson |
| |
| Affiliation: | School of Operations Research and Industrial Engineering, 206 Rhodes Hall, Cornell University, Ithaca, NY 14853, USA |
| |
| 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: | Approximation algorithms Derandomization Network design Rent-or-buy |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
