Browsing Combinatorics and Optimization by Subject "Approximation algorithms"

Now showing items 1-3 of 3

Approximation Algorithms for Clustering and Facility Location Problems

Ahmadian, Sara (University of Waterloo, 2017-04-06)

Facility location problems arise in a wide range of applications such as plant or warehouse location problems, cache placement problems, and network design problems, and have been widely studied in Computer Science and ...
Approximation Algorithms for Path TSP, ATSP, and TAP via Relaxations

Gao, Zhihan (University of Waterloo, 2015-07-29)

Linear programming (LP) relaxations provide a powerful technique to design approximation algorithms for combinatorial optimization problems. In the first part of the thesis, we study the metric s-t path Traveling Salesman ...
The Capacitated Matroid Median Problem

Kalhan, Sanchit (University of Waterloo, 2018-05-18)

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, ...