This decommissioned ERA site remains active temporarily to support our final migration steps to https://ualberta.scholaris.ca, ERA's new home. All new collections and items, including Spring 2025 theses, are at that site. For assistance, please contact erahelp@ualberta.ca.
Search
Skip to Search Results- 5Approximation algorithms
- 1Amortized analysis
- 1Clustering
- 1Combinatorial optimization
- 1Directed Steiner tree
- 1Facility location
-
Fall 2012
In this thesis, we present some approximation algorithms for the following clustering problems: Minimum Sum of Radii (MSR), Minimum Sum of Diameters (MSD), and Unsplittable Capacitated Facility Location. Given a metric (V, d) and an integer k, we consider the problem of partitioning the points...
-
Fall 2023
In this thesis, we design approximation algorithms for a variety of problems in Network Design. The first problem we consider is the Directed Steiner Tree (DST) problem where we want to find a cheapest way of connecting a subset of nodes (terminal nodes) from a root node in a directed network. We...
-
Spring 2019
Many real-world problems can be formulated as combinatorial optimization problems, thus making it very important to find efficient methods to solve them, both theoretically and practically. In this thesis, we consider several NP-hard combinatorial optimization problems, consisting of some...
-
Fall 2015
How to evaluate the performance of an algorithm is a very important subject in computer science, for understanding its applicability, for understanding the problem which it is applied to, and for the development of new ideas that help to improve the existing algorithms. There are two main...
-
Spring 2017
Budgeted Red-Blue Median is a generalization of classic k-Median in that there are two sets of facilities, say R and B, that can be used to serve clients located in some metric space. The goal is to open kr facilities in R and kb facilities in B for some given bounds kr,kb and connect each client...