Back to search

University of Waterloo

The Capacitated Matroid Median Problem

Abstract

dc:description.abstract

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' ⊆ F such that F' ∈ I, and figuring out an assignment i(j) ∈ F' for every j ∈ D such that each facility i ∈ F' 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. 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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kalhan, Sanchit
Advisor dc:contributor.advisor
  • Swamy, Chaitanya

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/13331

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kalhan, Sanchit. The Capacitated Matroid Median Problem. University of Waterloo, 2018. http://hdl.handle.net/10012/13331