<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.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-22T16:57:09Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/6758" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/6758</identifier><datestamp>2017-03-21T20:30:13Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="3088798f-7fe7-405d-8125-279059ee3b18" confidence="600">McAulay, Caelyn Burnham</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2012-05-19T01:02:02Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2012-05-19T01:02:02Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2012-05-19T01:02:02Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2012</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/6758</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Online algorithms are characterized by operating on an input sequence revealed over time versus a single static input. Instead of generating a single solution, they produce a sequence of incremental solutions corresponding to the input seen so far. An online algorithm&amp;apos;s ignorance of future inputs limits its ability to produce optimal solutions. The incremental nature of its solutions is also an obstacle. The two factors can be differentiated by examining the corresponding incremental algorithm, which has knowledge of future inputs, but must still provide a competitive solution at each step. &#xd;
&#xd;
In this thesis, the lower bound of the incremental constraint of k-server is shown to be to 2.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">computer science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">online algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">k-server</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">incremental algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">The Incremental Constraint of k-Server</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>