<?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-21T20:40:12Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/13331" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/13331</identifier><datestamp>2025-03-26T23:38:41Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</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="advisor">Swamy, Chaitanya</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="435909b5-a2a3-4579-8879-fe5230c7d765" confidence="600">Kalhan, Sanchit</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2018-05-18T19:38:56Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2018-05-18T19:38:56Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2018-05-18</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2018-05-16</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/13331</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In this thesis, we study the capacitated generalization of the Matroid Median Problem which is a generalization of the classical clustering problem called the k-Median problem. In the capacitated matroid median problem, we are given a set F of facilities, a set D of clients and a common metric defined on F ∪ D, where the cost of connecting client j to facility i is denoted as c_{ij}. Each client j ∈ D has a demand of d_j, and each facility i ∈ F has an opening cost of f_i and a capacity u_i which limits the amount of demand that can be assigned to facility i. Moreover, there is a matroid M = (F,I) defined on the set of facilities. A solution to the capacitated matroid median problem involves opening a set of facilities F&amp;apos; ⊆ F such that F&amp;apos; ∈ I, and figuring out an assignment i(j) ∈ F&amp;apos; for every j ∈ D such that each facility i ∈ F&amp;apos; is assigned at most u_i demand. The cost associated with such a solution is :  Σ_{i∈F} f_i +  Σ_{j∈D} d_j c_{i(j)j}. Our goal is to find a solution of minimum cost.&#xd;
As the Matroid Median Problem generalizes the classical NP-Hard problem called k- median, it also is NP-Hard. We provide a bi-criteria approximation algorithm for the capacitated Matroid Median Problem with uniform capacities based on rounding the natural LP for the problem. Our algorithm achieves an approximation guarantee of 76 and violates the capacities by a factor of at most 6. We complement this result by providing two integrality gap results for the natural LP for capacitated matroid median.</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">Approximation algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Matroid median</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">k-median</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">facility location</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">clustering</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">The Capacitated Matroid Median Problem</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Swamy, Chaitanya</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</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>