Back to search

Cornell University

God does not play dice... and neither should approximation algorithms

Abstract

dc:description.abstract

We consider optimization problems for which the best known approximation algorithms are randomized algorithms: these algorithms make random choices during their execution, and it has been shown that in expectation the cost of the algorithm's solution is at most a known constant factor more than optimal. We show how to give deterministic variants of these algorithms that have similar performance guarantees. In particular, we give conditions under which the Sample-Augment algorithms proposed by Gupta, Kumar, Pal and Roughgarden can be derandomized, thus obtaining the best known deterministic algorithms for a number of network design problems such as the connected facility location, virtual private network design and single sink buy-at-bulk problems. We also give deterministic variants of the ``pivoting" algorithms proposed by Ailon, Charikar and Newman for several ranking and clustering problems. In addition to obtaining the same performance guarantees, the analysis of our algorithms is actually simpler than that of their randomized counterparts. Finally, we take a more practical approach to one of the ranking problems considered: the rank aggregation problem. We perform an extensive evaluation of several known and new algorithms for rank aggregation on web search data. We argue that there are two important classes of algorithms for rank aggregation: positional methods and comparison sort methods. We find that hybrid algorithms, that combine a positional and comparison sort approach, work especially well on our data sets.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • van Zuijlen, Anke Renata

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
6397151

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

van Zuijlen, Anke Renata. God does not play dice... and neither should approximation algorithms. 2008. https://hdl.handle.net/1813/10883