<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-21T10:48:01Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/10883" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/10883</identifier><datestamp>2026-05-14T13:48:35Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">van Zuijlen, Anke Renata</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2008-06-06T17:49:22Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2013-06-06T06:17:08Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2008-06-06T17:49:22Z</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/10883</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">6397151</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">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. &#xd;
Finally, we take a more practical approach to one of the ranking problems considered: the rank aggregation problem.&#xd;
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.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en_US">en_US</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">approximation algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">derandomization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">rank aggregation</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">network design</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">consensus clustering</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">correlation clustering</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">feedback arc set in tournaments</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">God does not play dice... and neither should approximation algorithms</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">van Zuijlen, Anke Renata</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="97245701-85f8-432a-b7b8-8de8b568b7aa">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en_US&lt;/Language>
   	&lt;Title>God does not play dice... and neither should approximation algorithms&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2008-06-06T17:49:22Z&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>van Zuijlen, Anke Renata&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>approximation algorithms&lt;/Keyword>
    &lt;Keyword>derandomization&lt;/Keyword>
    &lt;Keyword>rank aggregation&lt;/Keyword>
    &lt;Keyword>network design&lt;/Keyword>
    &lt;Keyword>consensus clustering&lt;/Keyword>
    &lt;Keyword>correlation clustering&lt;/Keyword>
    &lt;Keyword>feedback arc set in tournaments&lt;/Keyword>
   	&lt;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&amp;apos;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&amp;quot; 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. &#xd;
Finally, we take a more practical approach to one of the ranking problems considered: the rank aggregation problem.&#xd;
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.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>